二分查找

# search


def search(li, item):
    """二分查找适用于有序列表"""

    n = len(li)
    if n == 0:
        return False
    # 从一半的位置开始找
    mid = n // 2
    # 那中间位置数据与要找的数据比较
    if item == li[mid]:
        return True
    elif item > li[mid]:  # 正序时，大于mid 往右找
        return search(li[mid + 1:], item)
    else:  # 正序时，小于mid 往左找
        return search(li[:mid], item)


if __name__ == '__main__':
    l = [1, 2, 3, 4, 5, 6]
    print(search(l, 1))
    print(search(l, 3))
    print(search(l, 6))
    print(search(l, 0))
    print(search(l, 9))

    # 时间复杂度：O(logn)