Python 中的二进制搜索导致无限循环

Question

list = [27 , 39 , 56, 73, 3, 43, 15, 98, 21 , 84]

found = False
searchFailed = False
first = 0
last = len(list) - 1
searchValue = int(input("Which number are you looking for? "))

while not found and not searchFailed:
    mid = (first + last) // 2
    if list[mid] == searchValue:
        found = True
    else:
        if first >= last :
            searchFailed = True
        else:
            if list[mid] > searchValue:
                last = mid - 1
            else:
                last = mid + 1

if found:
     print("Your number was found at location", mid)
else:
    print("The number does not exist within the list")

当我在搜索 27（第一个数字）时执行它时代码运行正常，但任何其他数字只会导致无限循环。我相信循环在第一次迭代时运行顺利，因为如果我将 first 的值更改为 1，代码会正确找到 39 的位置，但之后会重复所有其他数字的无限循环错误（而 27“不存在于循环”这是有道理的）。所以我想 mid 的值没有得到正确更新。

Answer 1

首先，不要使用任何保留字（此处list）来命名您的变量。其次，您在以下几行中存在逻辑错误：

if list[mid] > searchValue:
    last = mid - 1
else:
    last = mid + 1

上面代码段的最后一行，应该是first = mid + 1

Answer 2

这里要说明几点。首先，二分查找需要 sorted 数据才能工作。由于您的列表未未排序，因此可能会出现奇怪和欢闹 :-)

例如，当您正在寻找 39.

时，请考虑未排序的 [27 , 39 , 56, 73, 3, 43, 15, 98, 21]

第一个中点的值为 3，因此二分查找将完全丢弃左半部分（包括 3) since it expects 39to be to the right of that3. Hence it will never find 39`，尽管它在列表中。

如果您的列表未排序，您基本上只能进行顺序搜索。

其次，您应该根据比较结果更改 first 或 last。您在这两种情况下都更改 last，结果不会很好。

第三，使用标准数据类型名称或函数作为变量名称通常不是一个好主意。因为 Python 将 classes 和函数视为 first-class 对象，所以您可能会遇到绑定中断的情况：

>>> a_tuple = (1, 2) ; a_tuple
(1, 2)

>>> list(a_tuple)                  # Works.
[1, 2]

>>> list = list(a_tuple) ; list    # Works, unintended consequences.
[1, 2]

>>> another_list = list(a_tuple)   # No longer works.
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'list' object is not callable

解决这些问题，您的代码看起来像这样（在此过程中稍微重组）：

my_list = [3, 15, 21, 27, 39, 43, 56, 73, 84, 98]

found = False
first, last = 0, len(my_list) - 1
searchValue = int(input("Which number are you looking for? "))

while not found:
    if first > last:
        break
    mid = (first + last) // 2
    if my_list[mid] == searchValue:
        found = True
    else:
        if my_list[mid] > searchValue:
            last = mid - 1
        else:
            first = mid + 1

if found:
     print("Your number was found at location", mid)
else:
    print("The number does not exist within the list")

根据以下记录，这有效：

pax> for i in {1..6}; do echo; python prog.py; done

Which number are you looking for? 3
Your number was found at location 0

Which number are you looking for? 39
Your number was found at location 4

Which number are you looking for? 98
Your number was found at location 9

Which number are you looking for? 1
The number does not exist within the list

Which number are you looking for? 40
The number does not exist within the list

Which number are you looking for? 99
The number does not exist within the list

Answer 3

这个问题有很好的答案，你也可以考虑这个更简单的版本来适应你的情况：

my_list = [3, 15, 21, 27, 39, 43, 56, 73, 84, 98]  # sorted!

left, right = 0, len(my_list)  # [left, right)
search_value = int(input("Which number are you looking for? "))

while left + 1 < right:
    mid = (left + right) // 2
    if my_list[mid] <= search_value:
        left = mid
    else:
        right = mid

if my_list[left] == search_value:  # found!
     print("Your number was found at location", left)
else:
    print("The number does not exist within the list")

Answer 4

你的函数的问题是，在二进制搜索中，数组或列表需要 SORTED 因为它是二进制搜索最重要的原则之一，我做了同样的功能为您正常工作

#low is the first index and high is the last index, val is the value to find, list_ is the list, you can leave low as it is
def binary_search(list_: list, val,high: int, low: int = 0):
    mid = (low+high)//2
    if list_[mid] == val:
        return  mid
    elif list_[mid] <= val:
        return binary_search(list_, val, high+1)
    elif list_[mid] >= val:
        return binary_search(list_, val, high, low-1)

现在这是输出

>>> binary_search(list_, 21, len(list_)-1)
>>> 2

这里会发生的是，首先它会计算列表的中间索引，我认为你的列表是 5，然后它会检查中间值是否等于给搜索的值，然后return mid index，如果mid index小于value，那么我们会告诉它在high index上加1，我们做了index和value的比较，因为正如我告诉你的，list需要被排序，这意味着如果索引大于或等于中间索引，那么该值肯定也大于中间值，所以现在我们要做的是再次调用相同的函数，但这次使用更高的 high 这将增加中间点，如果这次中间索引等于值，那么它会 return 值并继续这样做直到中间等于值，并且在最后一个 elif 中它说如果中间值大于值，我们将再次调用相同的函数，但降低低点，即 0，现在为 -1，这将减少中点和 t他的整个过程会一直持续到mid等于value

Python 中的二进制搜索导致无限循环

Binary search in Python results in an infinite loop

python

infinite-loop

while-loop