Python实现二分查找运行异常，目标存在时返回None而非正确索引

• 二分查找的运行前提是待检索序列必须是有序的，你的二分查找代码逻辑没有错误，问题出在测试所用的列表未做排序处理。
• Python中字符串按照Unicode编码值逐位比较大小，你用到的测试列表["Sam", "John", "Martha", "Garrett", "Julia"]实际的升序排序结果为["Garrett", "John", "Julia", "Martha", "Sam"]，和你给出的列表顺序完全不一致，因此查找逻辑会走偏。

我们可以模拟你这次查找"Sam"的完整执行流程：

1. 初始状态：first=0，last=4，中点索引为(0+4)//2=2，对应元素为Martha，判定Martha < Sam为真，因此更新first=3
2. 第二次循环：first=3，last=4，中点索引为(3+4)//2=3，对应元素为Garrett，判定Garrett < Sam为真，因此更新first=4
3. 第三次循环：first=4，last=4，中点索引为4，对应元素为Julia，判定Julia < Sam为真，因此更新first=5
4. 此时first > last，循环终止，返回None

你只需要在执行查找前先对列表做排序即可，修改后的测试代码如下：

l = ["Sam", "John", "Martha", "Garrett", "Julia"]
# 先对列表做升序排序
l.sort()
print(binary_search(l, "Sam"))

排序后执行查找会正常返回Sam对应的索引4。如果你的业务场景不允许修改原列表顺序，建议改用线性查找，或者将原列表的元素和索引绑定后再排序检索。

内容的提问来源于stack exchange，提问作者Hayk Sahakyan