Python里实现二分查找算法

二分查找也称折半查找，它是一种效率较高的查找方法。但是二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。同时二分查找算法也是面试中经常会考到的一个算法，所以一定要弄清楚原理！二分查找的时间复杂度O(logn)，至于为什么是O(logn)，有兴趣的童靴可以查查推导方法。本文主要讲解Python里如何实现二分查找算法，分递归和非递归两种方式。具体代码如下：

# Autor: 5bug
# WebSite: http://www.5bug.wang

#二分查找非递归方式
def binarySearch(data, value):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == value:
            return mid
        elif data[mid] > value:
            high = mid -1
        else:
            low = mid + 1
    else:
        return None

#二分查找递归方式
def binarySearch2(data, value, low, high):
    if low <= high:
        mid = (low + high) // 2
        if data[mid] == value:
            return mid
        elif data[mid] > value:
            return binarySearch2(data, value, low, mid - 1)
        else:
            return binarySearch2(data, value, mid + 1, high)
    else:
        return None

if __name__ == "__main__":
    data = [1,3,4,5,6,6,7,9]
    print(binarySearch(data, 6))
    print(binarySearch(data, 8))

    print(binarySearch2(data, 6, 0, len(data) - 1))
    print(binarySearch2(data, 8, 0, len(data) - 1))

注意哦，一定得是以关键字为准的有序数据哦，另外如果元素重复，那么返回的是第一个的位置。