递归Binary_Search函数数组新增元素后返回-1问题求助

核心问题 #

你的二分查找函数逻辑本身没问题，但二分查找的核心前提是数组必须有序，而你测试用的数组[1,3,6,7,9,8]是无序的（末尾的8小于前面的9），这直接导致查找逻辑偏离预期，找不到明明存在的元素。

错误过程拆解 #

以你测试的查找元素8为例：

1. 初始low=0，high=5，计算中间索引M=(0+5)//2=2，对应元素6。8>6，所以low=3，进入下一轮递归。
2. 此时low=3，high=5，中间索引M=(3+5)//2=4，对应元素9。8<9，所以high=3，进入下一轮递归。
3. 此时low=3，high=3，中间索引M=3，对应元素7。8>7，所以low=4，进入下一轮递归。
4. 现在low=4 > high=3，触发返回None的逻辑（你标注的-1应为笔误）。

修复方案 #

方案1：传入有序数组 #

把测试数组改为升序排列的[1,3,6,7,8,9]，调用后就能正确返回元素8的索引4：

def Binary_Search(Data , low , high , item):
    if low <= high:
        M = (low+high)//2
        if Data[M]==item:
            return M
        elif item < Data[M]:
            high = M - 1
            return Binary_Search(Data ,low, high , item)
        else:
            low = M + 1 
            return Binary_Search(Data , low , high , item)
    else:
        return None
print(Binary_Search([1,3,6,7,8,9] , 0 , len([1,3,6,7,8,9])-1 , 8))
# 输出：4

方案2：调用前先排序 #

如果无法保证原始数组有序，可以在调用二分查找前先对数组排序（注意：排序后元素的原索引会改变，若需要原索引需额外处理）：

def Binary_Search(Data , low , high , item):
    if low <= high:
        M = (low+high)//2
        if Data[M]==item:
            return M
        elif item < Data[M]:
            high = M - 1
            return Binary_Search(Data ,low, high , item)
        else:
            low = M + 1 
            return Binary_Search(Data , low , high , item)
    else:
        return None

original_data = [1,3,6,7,9,8]
sorted_data = sorted(original_data)
print(Binary_Search(sorted_data , 0 , len(sorted_data)-1 , 8))
# 输出：4

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