二分查找

1.什么是二分查找?

二分查找(Binary Search): 又被称为折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区每次减少一半。

二分查找的时间复杂度：O(logn)

def binary_search(li, value):
    """
    li: 待查找列表
    value: 待查找的值
    """
    left, right = 0, li.__len__() - 1  # right是列表长度减一
    while left <= right:  # 表示候选区有值
        mid = (left + right) // 2
        if li[mid] == value:  # 找到了结果，直接返回
            return mid
        elif li[mid] < value:  # value在mid和right之间
            left = mid + 1
        else:
            right = mid - 1
    else:
        return None


res = binary_search(list(range(100)), 28)
print(res)