为何调用BinarySearch(x,14)时我的Python二分查找代码运行报错？

错误原因 #

你的代码里midpoint = (lower_bound + upper_bound)/2用了普通除法，结果是浮点数（比如第一次循环得到3.5），但numpy数组的索引必须是整数，所以访问Arr[midpoint]时会抛出索引错误。

修正方案 #

把除法改成整数除法//，或者用int()将midpoint转为整数：

import numpy as np

x = np.array([1,2,3,5,14,24,31,53])

def BinarySearch(Arr,search_value):
    lower_bound = 0
    upper_bound = len(Arr) - 1

    while lower_bound <= upper_bound:
        # 用整数除法//替代/，得到整数索引
        midpoint = (lower_bound + upper_bound) // 2
        midpoint_in_arr = Arr[midpoint]

        if search_value == midpoint_in_arr:
            return midpoint
        elif search_value < midpoint_in_arr:
            upper_bound = midpoint - 1
        elif search_value > midpoint_in_arr:
            lower_bound = midpoint + 1

    return -1

ans = BinarySearch(x,14)
print(ans)  # 输出4，对应数组中14的索引

补充说明 #

• 整数除法//会直接舍去小数部分，保证midpoint是整数，符合数组索引要求。
• 如果用普通除法，也可以通过midpoint = int((lower_bound + upper_bound)/2)强制转成整数，效果一致。

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