Python二分查找代码未返回预期结果，无法定位问题原因

问题根因 #

二分查找的核心前提是待搜索的序列为有序序列，你当前使用的测试数组arr = [1,24,5,3]是未排序状态，完全不满足二分查找的使用条件，自然无法得到预期结果。
你当前代码的执行逻辑如下：

• 初始参数：low=0，high=3，目标值5
• 第一次循环：mid=(0+3)//2=1，arr[1]=24大于5，因此更新high=mid-1=0
• 第二次循环：low=0<=high=0，mid=0，arr[0]=1小于5，因此更新low=mid+1=1
• 此时low=1>high=0，循环终止返回-1，输出Not present

修正方案 #

方案1：仅验证元素是否存在，不要求保留原数组下标 #

先对数组做升序排序后再调用二分查找即可：

def binary_search(l, low, high, val):
    while low <= high:
        mid = (high + low) // 2
        if l[mid] > val:
            high = mid - 1
        elif l[mid] < val:
            low = mid + 1
        else:
            return mid
    return -1


arr = [1,24,5,3]
# 先做升序排序
arr.sort()
result = binary_search(arr, 0,(len(arr)-1), 5)

if result == -1:
    print(" Not present")
else:
    print("given number present at index", result)

注：排序后数组变为[1,3,5,24]，此时返回的下标是2，和你预期的数值一致，但这是排序后数组的下标，不是原数组的下标。

方案2：需要获取原无序数组的对应下标 #

如果要保留原数组的下标关系，二分查找不适用，单次查找直接遍历数组即可：

arr = [1,24,5,3]
target = 5
result = -1
for idx, num in enumerate(arr):
    if num == target:
        result = idx
        break

if result == -1:
    print(" Not present")
else:
    print("given number present at index", result)

运行后会输出given number present at index 2，符合你的预期。

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