尝试搜索列表时出现二分查找错误

Question

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

现在我知道这个错误意味着什么了。只是我不明白我是如何遇到这个错误的。我尝试自己想象一下，结果非常好！

Answer 1

你的快速排序功能很好，让我修复二分搜索，我的代码返回正确的索引值：

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