Python二分查找返回None而非目标值问题排查求助

看起来你的二分查找代码遇到了几个关键问题，导致它总是返回None。让我一步步帮你排查和修复：

主要错误点 #

• 递归未返回结果：在BinarySearch方法中，你调用了递归但没有用return返回递归的结果。比如self.BinarySearch(mid, endIndex, A, target)这行，只是执行了递归，但没有把递归得到的索引返回给上层调用，导致当递归找到正确值时，上层函数无法获取这个结果，最终函数默认返回None。
• 空数组判断错误：len(A) == None是错误的写法，判断数组为空应该用len(A) == 0——因为len()函数返回的是整数，永远不会等于None。
• 二分边界调整不当：当前的递归边界调整（比如直接用mid作为新的startIndex或endIndex）可能导致死循环，正确的做法是搜索右半部分时用mid + 1，搜索左半部分时用mid - 1，避免重复检查同一个元素。
• 初始调用区间错误：原代码初始调用BinarySearch时传的endIndex是len(A)，但二分查找用全闭区间（0到len(A)-1）会更符合常规逻辑，避免越界风险。

修正后的代码 #

class Solution:
    def closestNumber(self, A, target):
        # 修正空数组判断逻辑
        if len(A) == 0:
            return -1
        # 修正边界条件：只有当目标值±1完全在数组范围外才返回-1
        if target + 1 < A[0] or target - 1 > A[-1]:
            return -1
        # 初始调用改为全闭区间：0到len(A)-1
        result = self.BinarySearch(0, len(A)-1, A, target)
        return result
    
    def BinarySearch(self, startIndex, endIndex, A, target):
        # 搜索区间不存在时，返回-1
        if startIndex > endIndex:
            return -1
        mid = (startIndex + endIndex) // 2
        # 找到目标值或相差±1的元素，直接返回索引
        if A[mid] == target or abs(A[mid] - target) == 1:
            return mid
        # 目标值+1大于当前mid值，递归搜索右半部分并返回结果
        if target + 1 > A[mid]:
            return self.BinarySearch(mid + 1, endIndex, A, target)
        # 目标值-1小于当前mid值，递归搜索左半部分并返回结果
        else:
            return self.BinarySearch(startIndex, mid - 1, A, target)

# 测试例子：返回4（对应元素20，和21的差为1）
print(Solution().closestNumber([1,4,6,10,20],21))

代码说明 #

1. 修复了递归调用的返回问题：每一次递归调用都用return传递结果，确保找到的索引能正确传递到上层函数。
2. 修正了空数组判断逻辑，避免语法错误。
3. 调整了二分查找的区间为全闭区间，并修正了递归时的边界调整，防止死循环。
4. 简化了目标值的判断逻辑：用abs(A[mid] - target) == 1直接判断是否相差±1，代码更简洁易读。

现在测试你的例子[1,4,6,10,20]和target=21，会正确返回4（对应元素20，和21的差为1）。

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