二分查找--基于python

简介

二分查找是查找中常用的算法，时间复杂度为O(logⁿ)(时间复杂度用来衡量一个算法查找的时间效率，是最糟糕的情况下的运行时间，衡量的是算法在随着输入的增加，查找的速度的增速)，相较于顺序查找O(n)，尤其是在数据量大的情况下，查找速度呈指数级别增长。其查找思想是每次取列表中间的元素与被查找的数进行比较（注意查找的前提是列表必须是有序的），如果该元素大于被查找数，则从列表左半部分继续查找（继续找中间的数），否则从右半部分查找，每次查找都能排除一半的元素，故效率非常高。

代码

def binary_search(my_list, item):
    low = 0  
    high = len(my_list) - 1 # 首先记录列表的首位和末尾索引，用以计算中间元素的位置
    while high >= low:  # 只要查找范围还没缩小到只包含一个元素，就继续查找
        mid = (high + low) // 2  # 中间元素的位置 `注意python3中用两个反斜线(地板除法)表示结果取整`
        guess = my_list[mid]  # 中间元素的值
        if guess == item:  # 如果中间元素就是被查找数，则该元素的位置就是最终结果
            return mid
        if guess > item:  # 如果该元素大于被查找数则从列表左半部分中继续查找
            high = mid - 1  #  将末尾的索引移到中间，由于中间数已经排除故可以往左挪一位
        else:  
            low = mid + 1 # 否则从列表右半部分继续查找
    return None  #最后找完整个列表也没找到，则返回None

验证

print( binary_search(my_list(-1,1,3,4,7,9), 7) )
4

print( binary_search(my_list(-1,1,3,4,7,9), 2) )
None