二分查找

二分查找是一种简单易懂的快速查找算法，二分查找要求必须有序。

算法实现

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = high - ((high - low) >> 1)
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

循环退出条件

当 low > high 就是循环退出

mid 取值

采用mid = high - (high - low) >> 1是为了防止 mid 溢出

low 和 high 的更新

对 low 和 high 进行+1 和-1 的操作，如果等于 mid，可能会造成死循环

复杂度

从上面这个例子可以查出来，查找的区间在不断的缩小，其中 k 为缩小的次数，时间复杂度就是O(logn)

    n, n/2, n/4, n/8, n/(2^k)

二分查找延伸

查找第一值等于给定值的元素

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = high - ((high - low) >> 1)
        if arr[mid] >= target:
            high = mid - 1
        else:
            low = mid + 1

    if low < len(arr) and arr[low] == target:
        return low
    return -1

查找最后一个值等于给定值的元素

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = high - ((high - low) >> 1)
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1

    if high < len(arr) and arr[high] == target:
        return high
    return -1

查找第一个大于等于给定值的元素

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = high - ((high - low) >> 1)
        if arr[mid] >= target:
            high = mid - 1
        else:
            low = mid + 1

    if low < len(arr):
        return low
    return -1

查找最后一个值小于等于给定值的元素

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = high - ((high - low) >> 1)
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1

    if high < len(arr):
        return high
    return -1