最近准备去找工作，时隔几年又要把在学校时代压床底的算法掏出来吹吹灰尘了，真有种朝花夕拾的感觉…哈哈哈哈
毕竟如果面试要是写不出来，那真是太尴尬了。

运行环境 Runtime environment

1
2
3

操作系统： Windos10  
IDE: JetBrains Python 2018.2.4 x64  
语言: Python 3.66

背景

我就说一句“要啥自行车？”。二分查找这玩意是啥查一查不是大把多解释的嘛？哈哈哈哈

算了，还是认真说一说吧。

使用情景

这并不难理解。举个例子:

我要查字典中的一个汉字，“哦”。
如果我按汉语拼音首字母从A一直翻到“哦”的汉语拼音首字母O，那将会是麻烦的一件事。
这种时候，一般都会从字典的后半部分开始找会比较快。
为什么呢？
因为我们都知道字典的字母排序是有规律的，而O在26个字母后半部分，优先从后半部分开始找比从头A开始找更有效率。
一半一半的排除，不断的缩小查找范围直到锁定目标，顾名思义这个就叫 二分查找 啦。

有序列表二分查找实现

在这里使用Python实现二分查找,代码如下：

def binary_search(tempList, tempItem):
    '''
    二分查找
    tempList：列表，被查找的列表对象
    tempItem：int，需要查找的元素
    range_min：int，范围最小值
    range_max：int，范围最大值
    '''
    range_min = 0  # 初始值，列表下标首位
    range_max = len(tempList) - 1  # 初始值，列表下标最末位
    times = 0  # 初始值，统计循环查找次数

    while range_min <= range_max:  # 只要范围没有缩小到剩唯一值就继续循环

        times += 1  # 记录一次查找

        mid = int((range_min + range_max) / 2)  # 求出列表下标中间值
        midItem = tempList[mid]  # 获取列表中间下表对应的元素

        if midItem == tempItem:  # 找到了,跳出循环，返回值
            return midItem,times

        if midItem > tempItem:  # 中间值大于目标元素
            range_max = mid - 1  # 则 范围最大值缩小到此中间值
        else:  # 否则 说明中间值小于目标元素
            range_min = mid + 1  # 则 范围最小值缩小到此中间值

    return None

if __name__ == '__main__':
    myLlist = list(range(1,101)) # 生成1~100的有序数字列表
    print(myLlist)
    myItem = int(input('输入一个1~100以内任意整数：'))
    res,mytimes = binary_search(myLlist,myItem)
    print('经过 %s 次 二分查找 找到了 %s '%(mytimes,res))

运行结果：

1
2
3

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
输入一个1~100以内任意整数：55
经过 7 次 二分查找 找到了 55