Python实现二分查找

前提：一个有序的列表
原理：假如我们心里默念一个1-100的数字，让别人猜，那么怎么猜会比较快呢？（1）从1开始往后猜，那么最坏的情况可能要猜100次；（2）每次都猜剩下数字列表的中间那个数，这样每次都可以排除一半，平均情况下，这种方法比第一种要快。
第二种方法也就是下面的二分查找算法（Python实现）。
时间复杂度：O(log2n)。

# -*- coding: UTF-8 -*-
# 二分查找 binary_search.py

def binary_search(list, item):
  low = 0
  high = len(list)-1  

  while low <= high:
    mid = (low + high) // 2
    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, 9) #结果：4
print binary_search(my_list, -1) #结果：None

以上代码只适用于没有重复数据的列表，如果列表中有重复的数据，我们要查找左边界或右边界，又该如何呢？在参考了 详解二分查找算法 之后，得出了一下代码供大家参考：

#  寻找左侧边界
def left_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            right = mid
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == len(list):
        return -1

    if list[left] == item:
        return left
    else:
        return -1


#  寻找右侧边界
def right_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            left = mid + 1
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == 0:
        return -1
    if list[left - 1] == item:
        return left - 1
    else:
        return -1