二分查找出现IndexError：列表索引越界问题求助

问题代码 #

def quickSort(arr):
  if len(arr) <= 1:
    return arr
  pivot = arr[int(len(arr)/2)]
  left = [x for x in arr if x < pivot]
  middle = [x for x in arr if x == pivot]
  right = [x for x in arr if x > pivot]
  return quickSort(left) + middle + quickSort(right)

def binSearch(sorted_arr, target):
  cen = int(len(sorted_arr)/2)
  if sorted_arr[cen] == target:
    return cen
  elif sorted_arr[cen] < target:
    return binSearch(sorted_arr[0:cen], target)
  else: 
    return binSearch(sorted_arr[cen:len(sorted_arr)], target)

my_array = [11, 9, 12, 7, 3, 8, 10, 2, 5, 1, 4, 6]
result = binSearch(quickSort(my_array), 13)
if result == -1:
  print("Element not found")
else:
  print(f"Element found at index {result}")

错误信息 #

line 12, in binSearch
  if sorted_arr[cen] == target:
IndexError: list index out of range

原因分析 #

1. 缺少递归终止条件：当目标值不存在于数组中时，递归会持续缩小数组范围，直到传入的sorted_arr变成空列表。此时len(sorted_arr) == 0，计算得到cen = 0，访问sorted_arr[0]自然触发索引越界。
2. 分支逻辑完全写反：
   • 当sorted_arr[cen] < target时，目标值应该在右侧子数组，但代码错误地传入了左侧子数组sorted_arr[0:cen]；
   • 当sorted_arr[cen] > target时，目标值应该在左侧子数组，但代码错误地传入了右侧子数组sorted_arr[cen:]。
     这种错误逻辑会导致递归不断向错误的方向缩小范围，最终快速触发空数组的情况。

举个具体推演：查找13时，排序后的数组是[1,2,3,4,5,6,7,8,9,10,11,12]，递归过程如下：

• 第一次：cen=6，值为7 <13 → 传入左侧子数组[1,2,3,4,5,6]
• 第二次：cen=3，值为4 <13 → 传入左侧子数组[1,2,3]
• 第三次：cen=1，值为2 <13 → 传入左侧子数组[1]
• 第四次：cen=0，值为1 <13 → 传入左侧子数组[]（空数组）
• 第五次：访问空数组的索引0，触发错误

修正后的代码 #

def quickSort(arr):
  if len(arr) <= 1:
    return arr
  pivot = arr[int(len(arr)/2)]
  left = [x for x in arr if x < pivot]
  middle = [x for x in arr if x == pivot]
  right = [x for x in arr if x > pivot]
  return quickSort(left) + middle + quickSort(right)

def binSearch(sorted_arr, target):
  # 添加空数组的终止条件，返回-1表示未找到
  if not sorted_arr:
    return -1
  cen = int(len(sorted_arr)/2)
  if sorted_arr[cen] == target:
    return cen
  elif sorted_arr[cen] < target:
    # 目标在右侧，传入cen+1到末尾的子数组
    right_idx = binSearch(sorted_arr[cen+1:], target)
    # 右侧子数组的索引要加上cen+1，对应原数组的全局索引
    return right_idx + cen + 1 if right_idx != -1 else -1
  else:
    # 目标在左侧，传入开头到cen的子数组
    return binSearch(sorted_arr[:cen], target)

my_array = [11, 9, 12, 7, 3, 8, 10, 2, 5, 1, 4, 6]
result = binSearch(quickSort(my_array), 13)
if result == -1:
  print("Element not found")
else:
  print(f"Element found at index {result}")

补充说明：修正后的代码不仅修复了逻辑错误，还处理了递归返回索引的偏移问题——子数组的索引和原数组的索引不一致，需要根据子数组的位置调整返回值，否则找到的索引会是子数组内的局部索引，而非原数组的全局索引。

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