Python有序列表二分查找函数问题求助：切片实现逻辑排查

你的代码无法正常运行，主要存在以下几个关键问题：

• 缺少循环/递归逻辑：二分查找需要重复执行「取中间元素-比较-缩小范围」的流程，你的代码只执行了一次该流程就终止，无法处理需要多次缩小范围的情况。
• 中间元素计算错误：len(arr)//2已经是列表的中间索引（索引从0开始），你额外减1导致取到的是中间位置的前一个元素，比如长度为5的列表，正确中间索引是2，你却取了索引1的元素。
• 范围划分逻辑完全颠倒：当target > a_m时，应该去**后半段（A_m至末尾）**查找，但你代码里将arr赋值为前半段arr[0:m]；反之target < a_m时应该去前半段，你却取了后半段，逻辑完全反了。
• 返回索引错误：即使找到元素，arr.index(a_m)返回的是切割后子列表的索引，不是原列表的真实索引，结果会出错。
• 未处理目标不存在的情况：如果遍历到列表为空仍未找到target，没有对应的返回逻辑，会引发错误。

修复后的代码（循环实现） #

def search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        m = (low + high) // 2  # 计算当前范围的中间索引
        a_m = arr[m]
        
        if target == a_m:
            return m  # 返回原列表的真实索引
        elif target > a_m:
            low = m + 1  # 去后半段查找
        else:
            high = m - 1  # 去前半段查找
    
    return -1  # 目标不存在时返回-1

代码说明 #

• 用low和high指针跟踪当前查找范围的边界，避免切割列表导致的索引偏移问题。
• 循环执行比较逻辑，直到找到目标或范围为空（low > high）。
• 找到目标时直接返回原列表的索引，不存在则返回-1，符合常规查找函数的行为。

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