Python实现-二分查找算法（3种方法）

如果有这样一个列表，让你从这个列表中找到66的位置，你要怎么做？
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
方法一：

lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
    num = input('请输入要查找的数：')
    if num.upper() == 'Q':
        print('结束查找！')
        break
    else:
        num = int(num)
        print('找到了，“{}”的位置是“{}”'.format(num, lst.index(num)))

运行结果：

请输入要查找的数：66
找到了，“66”的位置是“17”
请输入要查找的数：2
找到了，“2”的位置是“0”
请输入要查找的数：88
找到了，“88”的位置是“24”
请输入要查找的数：44
Traceback (most recent call last):
  File "D:/Python_Project/Temp.py", line 1872, in <module>
    print('找到了，“{}”的位置是“{}”'.format(num, lst.index(num)))
ValueError: 44 is not in list

如上，我们之所以用index方法可以找到，是因为Python帮实现了该查找功能，但index方法找不到时会直接报错，需要另外进行异常处理，并且如果index方法不给我们使用了，还能找到这个66吗？可以通过如下方法二来实现：
方法二：

lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
    num = input('请输入要查找的数：')
    if num.upper() == 'Q':
        print('结束查找！')
        break
    else:
        num = int(num)
        i = 0
        if num in lst:
            for n in lst:
                if n == num:
                    print('找到了，“{}”的位置是“{}”'.format(num, i))
                i += 1
        else:
            print('找不到“{}”这个值！'.format(num))

运行结果：

请输入要查找的数：66
找到了，“66”的位置是“17”
请输入要查找的数：2
找到了，“2”的位置是“0”
请输入要查找的数：88
找到了，“88”的位置是“24”
请输入要查找的数：44
找不到“44”这个值！
请输入要查找的数：q
结束查找！

如上方法既可以找到所需要查询的值，也可以处理找不到的值，但现在是怎么找到这个数的呢？是不是循环这个列表，一个一个的找的呀？假如我们这个列表特别长，有好几十万个数，甚至上百万、上千万等，那我们找一个数如果运气不好的话是不是要对比几十万次，甚至上百万、上千万次？这样效率太低了，我们得想一个新办法：二分查找算法。
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
观察下这个列表，这是不是一个从小到大排序的“有序”列表呀？
如果这样，假如我要找的数比列表中间的数还大，是不是我直接在列表的后半边找就行了？

这就是二分查找算法！
那么落实到代码上我们应该怎么实现呢？如下方法三：
方法三：

def find(lst, aim, start = 0 ,end = None):
    end = len(lst) if end is None else end
    mid_index = (end - start) // 2 + start      # 计算中间值
    if start > end:
        return None
    elif lst[mid_index] < aim:
        return find(lst, aim, start = mid_index + 1, end = end )
    elif lst[mid_index] > aim:
        return find(lst, aim, start = start, end = mid_index-1)
    else:
        return mid_index
lst = [2, 3, 5, 10, 15, 16, 18, 22, 26, 30, 32, 35, 41, 42, 43, 55, 56, 66, 67, 69, 72, 76, 82, 83, 88]
while 1:
    num = input('请输入要查找的数：')
    if num.upper() == 'Q':
        print('结束查找！')
        break
    else:
        num = int(num)
        ret = find(lst,num)
        if ret == None:
            print('找不到“{}”这个值！'.format(num))
        else:
            print('找到了，“{}”的位置是“{}”'.format(num, ret))

运行结果：

请输入要查找的数：66
找到了，“66”的位置是“17”
请输入要查找的数：2
找到了，“2”的位置是“0”
请输入要查找的数：88
找到了，“88”的位置是“24”
请输入要查找的数：44
找不到“44”这个值！
请输入要查找的数：q
结束查找！