二分查找详解

       二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

下面的示例说明了二分查找的工作原理，随便想一个1-100的数字，目标是以最少的次数猜到这个数字。每次猜测后，会提示小了、大了，或对了。

使用二分查找时，每次都猜中间的数字，从而每次都将余下的数字排除一半。

过程如下：100个元素>50>25>13?7>4>2>1.

代码：

def binary_search(list, item):
    """
    二分查找
    """

    low = 0                 # 第一个元素的位置
    high = len(list) - 1    # 最后一个元素的位置

    # 只要范围没有缩小到只包含一个元素，就一直循环下去
    while low <= high:
        mid = int((low + high) / 2)     # 一直检查中间的数, int是向下取整
        guess = list[mid]               # 猜的数一直在中间
        if guess == item:               # 如果猜的数对了, 就返回当前元素位置index
            return mid

        if guess > item:                # 如果猜的数大了, 则最大的数往左移, 排除掉一半的数
            high = mid - 1

        else:                           # 如果猜的数小了, 则最小的数往右移, 排除掉一半的数
            low = mid + 1

    return None                         # 若找不到目标数item, 返回None

my_list = [i for i in range(100)]
print(binary_search(my_list, 3))