Python迭代式Binary Search实现异常求助：仅拆分一次列表

核心问题分析 #

1. 原始列表未排序
   二分查找的核心前提是操作对象为有序列表，你提供的列表[3,6,8,12,14,17,25,29,31,36,42,47,63,55,62]末尾的63,55,62是无序状态，这会直接导致查找逻辑无法正确定位目标值。

2. 条件判断重复
   你的for循环里两个分支的判断条件完全一致：

if list[mid(list)] < key:
    list = list[mid(list)+1:]
elif list[mid(list)] < key:  # 这里应该是 > key
    list = list[mid(list)-1:]

第二个elif分支永远不会被触发，所以当第一次切片后，后续循环只会持续进入第一个分支，导致一直输出后半部分列表。

3. 变量名冲突
   使用list作为变量名会覆盖Python内置的list类型，这是不规范的编程习惯，可能引发后续代码的潜在问题，建议改用sorted_nums这类自定义名称。

4. 缺少目标值匹配后的终止逻辑
   当找到目标值key时，没有终止循环的逻辑，会继续执行不必要的切片操作。

修正后的代码 #

# 先确保列表是有序的
sorted_nums = sorted([3,6,8,12,14,17,25,29,31,36,42,47,63,55,62])
key = 42
print("初始有序列表:", sorted_nums)

def high(sorted_list):
    return len(sorted_list)
    
def low(sorted_list):
    return 0  

def mid(sorted_list):
    # 简化mid计算，和原逻辑等价
    return (low(sorted_list) + high(sorted_list)) // 2

# 替换硬编码循环，改为动态循环直到找到或范围为空
current_list = sorted_nums.copy()
while current_list:
    mid_idx = mid(current_list)
    mid_val = current_list[mid_idx]
    if mid_val < key:
        current_list = current_list[mid_idx+1:]
    elif mid_val > key:
        current_list = current_list[:mid_idx]  # 取左半部分，避免丢失元素
    else:
        print(f"找到目标值 {key}")
        break
    print("当前列表:", current_list)
else:
    print(f"未找到目标值 {key}")

额外说明 #

• 修正了切片逻辑：当mid值大于key时，应该取列表的前半部分current_list[:mid_idx]，而不是mid_idx-1:，否则会丢失mid_idx之前的元素。
• 改用while循环替代硬编码的for循环，让查找逻辑更通用，能处理任意长度的有序列表。

内容的提问来源于stack exchange，提问作者Lil M