Python递归实现二分查找传参为空触发索引越界报错排查

问题现象 #

实现递归二分查找时，预期向右半段递归传入子列表[5,9,12]，实际传入空列表[]，导致取中间索引0位置的元素时触发索引越界，报错栈如下：

File "C:\Users\wesch\Desktop\bs.py", line 5, in search
    currentMiddleValue = nums[currentMiddleIndex]
  File "C:\Users\wesch\Desktop\bs.py", line 10, in search
    return self.search(nums[currentMiddleIndex:len(nums)], target)
  File "C:\Users\wesch\Desktop\bs.py", line 16, in <module>
    print(test.search([-1,0,3,5,9,12], 9)) 

原始问题代码：

class Solution:
    def search(self, nums: list, target: int) -> int:
        #nums = nums[currentMiddleIndex:len(nums)]
        currentMiddleIndex = int((len(nums)) // 2)
        currentMiddleValue = nums[currentMiddleIndex]
        nums = nums[currentMiddleIndex:len(nums)]
        if currentMiddleValue == target:
            return nums.index(currentMiddleValue)
        elif currentMiddleValue < target:
            return self.search(nums[currentMiddleIndex:len(nums)], target)
        elif currentMiddleIndex == 0:
            return -1
        else: 
            return self.search(nums[0:currentMiddleIndex], target)
test = Solution()
print(test.search([-1,0,3,5,9,12], 9))

根因分析 #

• 核心传参错误：切片时机完全混乱。计算完当前层的中间索引currentMiddleIndex后，未做分支判断就提前执行nums = nums[currentMiddleIndex:len(nums)]，把当前层的原列表直接截断成了右半段子列表。以第一次调用为例：原列表长度6，中间索引为3，对应值为5，执行完截断代码后nums变为长度3的[5,9,12]；此时判断目标值9大于5，需要传入右半段递归，代码再次执行nums[currentMiddleIndex:len(nums)]切片，此时currentMiddleIndex还是之前计算的3，但新nums长度只有3，从索引3位置开始切片超出列表范围，直接返回空列表传入下一层，触发崩溃。
• 终止条件逻辑缺陷：将currentMiddleIndex == 0的终止判断放在分支逻辑靠后位置，无法在空列表进入函数时提前拦截，会先执行取中间值的代码触发越界。
• 返回值逻辑错误：使用nums.index(currentMiddleValue)返回的是子列表内的相对索引，不是目标值在原列表的真实下标，即使不触发崩溃，搜索返回的索引结果也是错误的。

修正方案 #

去掉提前截断nums的冗余逻辑，补全空列表终止判断，给右半段递归结果加偏移量修正下标，修正后代码如下：

class Solution:
    def search(self, nums: list, target: int) -> int:
        # 空列表直接返回-1，提前终止避免越界
        if not nums:
            return -1
        currentMiddleIndex = len(nums) // 2
        currentMiddleValue = nums[currentMiddleIndex]
        if currentMiddleValue == target:
            return currentMiddleIndex
        elif currentMiddleValue < target:
            # 右半段从中间索引下一位开始切，返回结果要加偏移量修正原列表下标
            sub_res = self.search(nums[currentMiddleIndex+1:], target)
            return sub_res + currentMiddleIndex + 1 if sub_res != -1 else -1
        else:
            # 左半段直接切到中间索引前，下标和子列表一致无需偏移
            return self.search(nums[:currentMiddleIndex], target)

test = Solution()
print(test.search([-1,0,3,5,9,12], 9))
# 运行输出4，与目标值9在原列表的下标一致

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