Python二分查找异常：数字字符串与字母字符串的字典序优先级问题

问题背景 #

你编写的二分查找代码如下：

inventory=["10", "50", "100", "150", "200"]

SearchItem=input("Enter item: ")

LB=0
UB=len(inventory)-1
Found=False

while Found==False and LB <= UB:
    Mid=(LB + UB)//2
    if inventory[Mid]==SearchItem:
        print("Item found in the position: ", Mid + 1)
        Found=True
    elif SearchItem>inventory[Mid]:
        LB= Mid + 1
    else:
        UB= Mid - 1

if Found==False:
    print("Item doesn't exist.")

当inventory为["a", "10", "50", "100", "200"]时输入"a"会提示未找到；改为["10", "50", "100", "200", "a"]时输入"a"能找到位置5，核心原因和字典序规则如下：

1. 两种情况结果不同的原因 #

二分查找的核心前提是目标列表必须按照比较规则有序排列，你的两个列表在字典序下的有序性不同：

• 第一个列表["a", "10", "50", "100", "200"]是无序的：按照字典序，"a"的优先级低于所有数字字符串，应该排在列表末尾而非开头，此时二分查找逻辑被打乱：
  1. 初始中间位置是索引2（值为"50"），"a"比"50"大，左边界LB设为3；
  2. 新的中间位置是索引3（值为"100"），"a"仍比"100"大，LB设为4；
  3. 中间位置是索引4（值为"200"），"a"还是比"200"大，LB设为5，此时LB>UB，循环结束，判定未找到。
• 第二个列表["10", "50", "100", "200", "a"]符合字典序：数字字符串在前，字母字符串在后，二分查找能正常遍历到目标位置：
  1. 中间位置索引2（"100"），"a"更大，LB设为3；
  2. 中间位置索引3（"200"），"a"更大，LB设为4；
  3. 中间位置索引4（"a"），匹配成功，返回位置5。

2. 字典序中数字与字母字符串的优先级 #

在Python中，字符串比较基于字符的Unicode编码值：

• 数字字符（'0'-'9'）的Unicode编码范围是U+0030到U+0039；
• 小写字母（'a'-'z'）的Unicode编码范围是U+0061到U+007A；
  编码值越小优先级越高，因此数字字符串的优先级比小写字母字符串更高，比如直接比较"10" < "a"会返回True。

内容的提问来源于stack exchange，提问作者AHM Mamun