Python中二分查找的实现

writer：lIcht                      email：lIcht.gzl@gmail.com                 Date:  2019.9.15

        二分查找是一种基础的数据搜索方法，比起对整个数据类型对象的遍历，减少了最坏时间复杂度，提高了查找效率，但是也对待查找的队列有一定要求，即必须是有序的顺序表。在Python中可通过迭代的方法以及不使用迭代使用游标(指针)的思想实现。

xxxxxxxxxx
# 二分查找
# 先要条件：所在序列必须是有序顺序表
# 最优时间复杂度：O(1)
# 最坏时间复杂度：O(logn)
​
​
def binary_search(alist, item):
    """二分查找,递归"""
    n = len(alist)
    if n > 0:
        mid = n//2
        if item == alist[mid]:
            return True
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        else:
            return binary_search(alist[mid+1:], item)
    return False
​
​
def binary_search2(alist, item):
    """二分查找，非递归"""
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last) // 2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False
​
​
if __name__ == "__main__":
    li = [17, 26, 30, 31, 54, 55, 65, 93]
    print(binary_search(li, 17))
    print(binary_search(li, 88))
    print(binary_search2(li, 93))
    print(binary_search2(li, 88))
​