Python 二进制搜索 while 循环不会中断

Question

我在 Python 上使用二分查找来解决以下问题：你有一个包含 n 个正整数的列表：a0、a1、a2、... an-1，按升序排列。

现在，你的朋友要问你 m 个问题，每个问题的形式是 "Here is a positive integer B. Is B a part of the list?"

如果B在列表a中，你会说"Yes"。

你的任务是输出你对任何给定输入说“是”的次数。

1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5 和 1 ≤ A, B ≤ 10^9

我编写了以下代码：

n = int(raw_input())
a = [int(x) for x in raw_input().split()]
m = int(raw_input())

answer = 0

lo = 0
hi = len(a) - 1
end = False

for i in range(0, m):
    B = int(raw_input())
    while (lo <= hi):
        mid = int((lo + hi) / 2)
        if B == a[mid]:
            answer = answer + 1
            break
        elif B < a[mid]:
            hi == mid - 1
        elif B > a[mid]:
            lo == mid + 1

print answer

我在终端测试了它，它从来没有输出答案，相反，我只是不停地在终端中输入数字（甚至字母）。 n、a、m 和 B 的第一个值的输入已经成功，因为如果我键入一个字母，终端会给我错误消息，但是在前 4 行之后，它只是不响应我键入的任何内容，直到我使用ctrl Z 跳出 Python.

有人能解释一下为什么会这样吗？我也手动测试了这个程序，它应该可以工作。

谢谢。

Answer 1

代码的一个问题如@JohnnyMopp 所评论：您应该使用 = 进行赋值，而不是 == 相等运算符。

另一个问题是 hi 和 low 的值在每次二进制搜索后都不会重置。您应该将初始化这些变量的行移动到 for 循环中：

answer = 0

for i in range(0, m):
    B = int(raw_input())
    lo = 0
    hi = len(a) - 1

    while (lo <= hi):
        mid = int((lo + hi) / 2)
        if B == a[mid]:
            answer = answer + 1
            break
        elif B < a[mid]:
            hi = mid - 1
        elif B > a[mid]:
            lo = mid + 1

print answer

一个更好的主意是将二分搜索写成一个函数。

无需编写自己的二进制搜索即可实现此目的的另一种方法是使用 bisect.bisect():

import bisect

def bisect_in(l, v):
    return v == l[bisect.bisect(l, v)-1]

count = 0
for i in range(m):
    B = int(raw_input())
    count += bisect_in(a, B)

print count

Python 二进制搜索 while 循环不会中断

Python Binary Search while loop doesn't break

python

loops

binary-search

while-loop

binary-search-tree