python 中的二进制搜索程序不会停止循环

Question

如果提供给定值，我正在尝试对 list/array 进行二进制搜索。这是我的代码：

item = "dog"
list = ["banana","dog","apple","britain","light","error","brother"]
length = len(list)
guess = (length + 1) // 2
counter = 0
while list[guess] != item:
    counter = counter + 1
    print("False")
    if guess < list.index(item):
        for i in range(guess):
            del list[i]
    else:
        largest = list[-1]
        for i in range(guess, list.index(largest)):
            del list[i]
    length = len(list)
    guess = (length + 1) // 2
print(f"I found {list[guess]} and it took {counter} tries.")

我想让它在我的列表中执行二分搜索 "dog" 这个词，但它陷入了困境，只是循环并连续打印 false 。我不知道为什么。

如果有人可以更正我的代码并告诉我哪里出了问题，我们将不胜感激。

Answer 1

我写了一个函数来做 bs，我只是想回答这个问题，但现在我认为最好告诉你应该如何进行二进制搜索。

让my_list = [2, 4, 1, 6, 3, 5]和我们的项目5。为了进行二进制搜索，我们首先需要对列表进行排序，所以在我们的例子中 my_list = [1, 2, 3, 4, 5, 6].

您需要跟踪两个位置，我们将它们称为 lo 和 hi，分别代表最低价和最高价。我们初始化 lo = 0 和 hi = len(my_list) - 1

[1, 2, 3, 4, 5, 6]
 l              h
 0              5

然后我们将两者的中间值计算为 mid = (hi+lo) // 2，在本例中为 mid = 2。 (a//b 等同于 math.floor(a/b))

我们现在将项目 (5) 与 my_list[mid] (3) 进行比较，我们的项目更大，因此我们知道项目的位置必须高于 mid 所以我们可以说 lo = mid + 1

[1, 2, 3, 4, 5, 6]
          l     h
          3     5

我们重新计算 mid = (lo + hi // 2) 和 mid = 4。我们比较my_list[mid](5)和item(5)可以知道item的index是mid.

这个解释很含糊，你必须考虑是应该做lo = mid + 1还是只做lo = mid，当项目低于中间时会发生什么，当项目不在中间时会发生什么名单。但是既然你在研究这个，我就让你好好想想。

希望对您有所帮助！

python 中的二进制搜索程序不会停止循环

Binary search program in python won't stop looping

python

algorithm

binary-search

python-3.x