Python3查找算法02 - 二分查找

原创
Madman
/
2018-09-10T07:51:00Z
/
0
8713 次阅读

Synopsis: 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表

代码已上传到 https://github.com/wangy8961/python3-algorithms ，欢迎star

1. 二分查找

二分查找（binary search），也称折半查找（half-interval search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程为，从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果要查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半

2. 非递归实现

def binary_search(L, item):
    '''非递归实现二分查找，输入的列表必须是有序的（比如，从小到大排列）'''
    first = 0
    last = len(L) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        print('first = {}, last = {}, midpoint = {}'.format(first, last, midpoint))  # 测试
        if L[midpoint] == item:  # 找到了
            found = True
        else: