二分查找

应用场景

1.现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名karlmageddon，Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。

2.从100里猜数字，最少只需要猜几次？

What

二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

Why

对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。

How

Python实现：写一个函数，这个函数接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个 函数将返回其位置。

def binary_search(list, item):
  # low and high keep track of which part of the list you'll search in.
  low = 0
  high = len(list) - 1

  # While you haven't narrowed it down to one element ...
  while low <= high:
    # ... check the middle element
    mid = (low + high) // 2
    #得到商，并向下取整，比如3.5变成3；每次都检查中间的元素
    guess = list[mid]
    # Found the item.
    if guess == item:#找到了元素
      return mid
    # The guess was too high.修改high
    if guess > item:
      high = mid - 1
    # The guess was too low.修改low
    else:
      low = mid + 1

  # Item doesn't exist
  return None#没有指定的元素

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

# => 1，返回3所在列表的索引位置，从0开始，所以3返回1；
#体会一下这种测试驱动开发的思想，先在代码后面写上用于测试的语句；
#先用伪代码理清逻辑，然后再补充好细节；

# 'None' means nil in Python. We use to indicate that the item wasn't found.
print (binary_search(my_list, -1)) 
# => None，因为不存在，所以返回None；

输出：
1
None

自我检测

这里列举常见的关于这个知识点的问题。