二分查找是如何工作的？

Question

我正在通过this website.学习python

这是一个很棒的资源，但是当他解释时 binary searches 我有点困惑。

这是他提供的用于搜索超级反派名字文本文件的代码：

file = open("super_villains.txt")

name_list = []
for line in file:
    line = line.strip()
    name_list.append(line)

file.close()

# Binary search
key = "Morgiana the Shrew"
lower_bound = 0
upper_bound = len(name_list)-1
found = False
while lower_bound <= upper_bound and not found:
    middle_pos = (lower_bound+upper_bound) // 2
    if name_list[middle_pos] < key:
        lower_bound = middle_pos + 1
    elif name_list[middle_pos] > key:
        upper_bound = middle_pos - 1
    else:
        found = True

if found:
    print("The name is at position", middle_pos)
if not found:
    print("The name was not in the list.")

这是让我感到困惑的部分：if name_list[middle_pos] < key: python 在不知道我们要查找的键的位置的情况下，怎么可能知道索引中的某个位置是大于还是小于键的位置？

这感觉像是一个愚蠢的问题，但我不明白当我们不知道其中一个位置时如何比较数组中的两个位置。

Answer 1

二进制搜索的一个关键是它正在搜索一个排序列表，在这种情况下，我相信它假设它是按字母顺序排序的。

考虑到这一点，if 语句实际上是在比较字符串，而不是数字，这意味着它正在查看当前键是在当前中间位置之前还是之后。然后一旦找到，它就会将位置减半，直到找到钥匙的位置。

Answer 2

它假定列表 name_list 已排序。然后，如果位于 middle_pos 的名称按字母顺序出现在我们要搜索的名称之前（在本例中为 key），我们知道我们可以跳过从 lower_bound 到 middle_pos 的所有名称.

Answer 3

name_list[middle_pos] 将是一些值，例如 Ratigan the Rat。在你的例子中 key 是 Morgiana the Shrew.

比较name_list[middle_pos] < key将决定Ratigan是否在Morgiana之前。由于他不是（按字母顺序排列），因此我们将搜索范围缩小到他之前的名字范围，并将其切成两半。然后再问一遍，缩小范围。

您不断缩小范围，直到只剩下一个值。它要么正确，要么不正确。如果不是，则 Morgiana 根本不在列表中。或者我们找到了她的索引。

二分查找是如何工作的？

How does binary search work?

python

binary-search