Python二进制搜索实现中的边界搜索项

Question

我已经以不同的方式在Python中实现了二进制搜索，并且我正在对已排序的列表进行测试。当搜索项超出列表的最小值和最大值的范围时，迭代解决方案将失败。

我已经做了一些初步的测试和调试。我无法理解实施中的问题。

def bisect_search_itr(L, e):
  low = 0
  high = len(L)
  mid_index = (low + high) // 2
  while low <= high:
    if L[mid_index] == e:
      return True
    else:
      if e > L[mid_index]:
        low = mid_index
      else:
        high = mid_index
    mid_index = (low + high) // 2
  return False

def bisect_search_rec(L, e):
  if L == []:
    return False
  elif len(L) == 1:
    return L[0] == e
  else:
    half = len(L) // 2
    if L[half] > e:
      return bisect_search_rec(L[:half], e)
    else:
      return bisect_search_rec(L[half:], e)

def bisect_search_rec_with_bounds(e, m, n):
  if m == n:
    return L[m] == e
  else:
    half = m+n//2
    if L[half] == e:
      return True
    else:
      if e < L[half]:
        return bisect_search_rec_with_bounds(e, m, half)
      else: 
        return bisect_search_rec_with_bounds(e, half, n)

# Test case
L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
x = 17

print(bisect_search_itr(L, x))
print(bisect_search_rec(L, x))
print(bisect_search_rec_with_bounds(x, 0, len(L) - 1))

递归实现效果很好，但是对于迭代实现，它会陷入无限循环。

Answer 1

取决于您要如何实现，可以返回最接近的数字（15），也可以引发错误。