二进制搜索如何工作？(How does binary search work?)

二进制搜索如何工作？(How does binary search work?)

我正在通过这个网站学习python 。

这是一个很棒的资源，但当他解释二进制搜索时，我有点困惑。

这是他提供的用于搜索超级恶棍名称文本文件的代码：

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:我感到困惑的一部分： if name_list[middle_pos] < key: python怎么可能知道索引中的某个位置是否大于或小于键的位置，而不知道键的位置我们正在找？

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

I am learning python through this website.

It's a fantastic resource, but when he explains binary searches I am left a little confused.

This is the code he supplies to search through a text file of super-villain names:

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.")

This is the part that has left me confused: if name_list[middle_pos] < key: How could python possibly know if a certain position in the index is greater or lesser than the position of the key, without already knowing the position of the key we're looking for?

This feels like a dumb question, but I don't understand how you can compare two positions in an array when we don't know one of them.

最满意答案

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

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

One key thing for binary searches is that it is searching through a sorted list, in this case, I believe that it is assuming that is in sorted alphabetically.

With this in mind, that if statement is actually comparing strings, not numbers which means that it is looking whether the current key is before or after the current middle pos. Then once it finds out, it will half the positions until it has found the position of the key.