python - 为什么这个二分搜索算法两次返回 None ？

Question

我开始学习算法(使用 grokkings 算法书)，这是书中的二分搜索代码

def binary_search(list, item):

  low = 0
  high = len(list) - 1

  while low <= high: 
    mid = round((low + high) )
    guess = list[mid]
    
    if guess == mid:
      return mid

    if guess > mid: 
      high = mid - 1 

    else: 
      low = mid + 1

  return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

第一个应该返回 1 但它返回 None 两次，有人知道为什么吗？

Answer 1

尝试将猜测与项目进行比较:

def binary_search(lst, item):
    low = 0
    high = len(lst) - 1
    while low <= high: 
        mid = (low + high) // 2
        guess = lst[mid]
        if guess < item:
            low = mid + 1
        elif guess > item: 
            high = mid - 1
        else:
            return mid
    return None


my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

输出:

1
None