二叉树解释为什么这样做

Question

开始阅读使用此示例代码的有关基本数据结构和算法的书，

    def binary_search(list, item):
    low = 0  
    high = len(list)-1  #sets upper range to length of provided list

    while low <= high:
        mid = (low + high) #why does (low + high) give me middle of list?
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            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)

虽然我理解树的概念，但我不明白为什么

mid = (low + high) #why does (low + high) give me middle of list？ low + high 不会给我和 high 一样的价值吗？我不应该需要 low + high / 2 来找到中点吗？但它工作得很好吗？

Answer 1

之所以有效，是因为 mid 总是在正确的范围内，但这是线性搜索，而不是二进制搜索。您可以通过打印检查的索引来检查这一点：

def binary_search(list, item):
    low = 0  
    high = len(list)-1  #sets upper range to length of provided list

    while low <= high:
        mid = (low + high) #why does (low + high) give me middle of list?
        print("mid =", mid)
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1

在您的示例中寻找 -1：

>>> print (binary_search([1,3,5,7,9],-1))
mid = 4
mid = 3
mid = 2
mid = 1
mid = 0
None

所以你是对的：你应该将 mid 除以 2（并避免使用 list 作为变量名）。

Answer 2

确实应该是(low+high)//2。现在，mid 从列表中的最后一项开始，并始终通过 guess>item 条件的 else 部分。所以 high 每次都减 1 并且 low 永远不会改变（从零开始）。该过程最终会从最后到第一个遍历所有元素，这根本不是二进制搜索（而是顺序搜索）。

Answer 3

你是对的，这是不正确的！

它会给你正确的结果，但让我们看看实际发生了什么。

  if guess == item:
    return mid
  if guess > item:
    high = mid - 1
  else:
    low = mid + 1

在第一次迭代中，guess == list[mid] == list[high] == 9。 3小于9，所以高会递减。

在下一次迭代中，再次mid == high，但high减1。

high 将继续递减，直到 guess == list[mid] == list[high] == list[1] == 3

二叉树解释为什么这样做

binary tree explanation why does this work

python

binary-search