二分查找

也叫折半查找，从有序列表的候选区li[0:n]开始，通过对 待查找的值和候选区中间值的比较，可以使候选区的值减少一半

候选区

1. left和right定义候选区的左侧下标和右侧下标
2. mid代表了候选区的中间值

代码实现

def binary_search(li, val):
    """
    二分查找
    :param li: 有序列表
    :param val: 要查找的值
    :return: 返回下标或者None
    """
    # 定义初始候选区
    left = 0
    right = len(li)-1

    while left <= right:
        mid = (left+right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] < val:  # 要查找的值在右侧可能存在
            left = mid + 1
        else:   # 要查找的值在左侧可能存在
            right = mid - 1
    else:   # 要找的值不在有序列表中
        return None


print(binary_search([1, 3, 4, 6, 7, 9], 7))

总结

• 时间复杂度: O(logn)