练习编写的简易binary search算法无法运行，请求协助排查

你的二分查找代码有三个关键问题，导致它要么返回None，要么给出错误索引：

• 递归分支未返回结果：当arr[mdpt] > k或arr[mdpt] < k时，你调用了递归的binarysearch，但没有用return把递归结果传递回上层函数，最终上层函数没有返回值，输出None。
• 冗余且低效的存在性检查：开头的if k not in arr会遍历整个数组，直接把二分查找O(logn)的效率降到O(n)，而且递归时传递的是子数组，这个检查会误判——比如原数组存在目标值，但当前子数组里没有，就直接返回-1，跳过了正确的递归分支。
• 切片导致的索引偏移：每次递归传递子数组，返回的是子数组内的索引，不是原数组的索引。比如找原数组里的4（索引3），第一次递归会传递子数组[3,4,5]，在子数组里4的索引是1，最终返回的1和原数组的3完全不符。

修复后的代码 #

def binarysearch(arr, k):
    def helper(left, right):
        # 边界：左指针超过右指针，说明没找到
        if left > right:
            return -1
        # 计算中间索引，用//避免浮点问题
        mdpt = (left + right) // 2
        if arr[mdpt] == k:
            return mdpt
        elif arr[mdpt] > k:
            # 目标在左半区，递归左半区
            return helper(left, mdpt - 1)
        else:
            # 目标在右半区，递归右半区
            return helper(mdpt + 1, right)
    # 初始调用：左边界0，右数组最后一个元素的索引
    return helper(0, len(arr) - 1)

arr = [1, 2, 3, 4, 5]
k = 2
print(binarysearch(arr, k))  # 输出1

修复说明 #

1. 用内部辅助函数helper传递原数组的左右边界，避免切片带来的索引偏移和额外内存消耗。
2. 去掉了冗余的k not in arr检查，改用left > right判断目标值不存在，完全符合二分查找的逻辑。
3. 所有递归调用都加上return，确保结果能正确向上传递。
4. 用(left + right) // 2计算中间索引，比int((n-1)/2)更简洁，也能处理偶数长度的数组。

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