在列表中搜索时的二分查找错误

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)

Answer 2

你的递归二分查找的实现有问题。

这里有一个改进的版本：

def binSearch(_list, _item):
    def _binSearch(_list, lo, hi):
        nonlocal _item
        if hi >= lo:
            mid = (hi + lo) // 2
            if _list[mid] == _item:
                return mid
            elif _list[mid] > _item:
                return _binSearch(_list, lo, mid - 1)
            else:
                return _binSearch(_list, mid + 1, hi)
        return -1
    if _list and _item >= _list[0] and _item <= _list[-1]:
        return _binSearch(_list, 0, len(_list)-1)
    return -1

用这个版本时，你只需要传入一个（已经排好序的）列表和你要找的项目。

不过，递归的二分查找通常会比迭代的方法慢，比如：

def binSearch(slist, item):
    if slist and item >= slist[0] and item <= slist[-1]:
        lo = 0
        hi = len(slist) - 1
        while lo <= hi:
            m = (lo + hi) // 2
            mv = slist[m]
            if mv == item:
                return m
            if mv < item:
                lo = m + 1
            else:
                hi = m - 1
    return -1

如果你想要最佳的性能，我建议：

from bisect import bisect_left

def binSearch(slist, item):
    if slist and item >= slist[0] and item <= slist[-1]:
        i = bisect_left(slist, item)
        if i != len(slist) and slist[i] == item:
            return i
    return -1

Answer 3

简单来说，你的二分查找函数里没有设置一个结束的条件。它一直在把你的数组一分为二。你需要加一个结束的条件，来检查你的数组长度是否为0。

if len(sorted_arr) == 0:
    return -1

想了解更多关于二分查找的内容，可以查看这里