python - 二分查找是如何工作的？

Question

我正在通过 this website. 学习 python

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

这是他提供的用于搜索 super 反派名字的文本文件的代码:

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 语句实际上是在比较字符串，而不是数字，这意味着它正在查看当前键是在当前中间位置之前还是之后。然后一旦找到，它将位置减半，直到找到 key 的位置。