参考：https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/

1 基本介绍

二分查找法（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。其基本思想是，首先将整个有序数列分成前后两部分，判断在哪个部分中可能会找到要查找的数，然后递归地在那个部分中查找。

具体来说，首先选择数列的中间元素。如果要查找的数比中间元素小，则在数列的左半部分继续查找；如果要查找的数比中间元素大，则在数列的右半部分继续查找；如果相等，则找到了要查找的数。这样一直递归进行，直到找到要查找的数或者整个数列被查找完。

二分查找法的时间复杂度为 O(log n)，其中 n 是数列中的元素个数。由于其在有序数列中查找元素的时间复杂度较低，因此常用于大规模有序数列的查找。

二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。

• 有哪些细节：

while循环中使用 low <= high 还是 low < high ？

if条件里写<还是<=? 是low = mid +1？

还是low = mid ？

2 基本的二分查找

基本的二分查找中有序数组里的元素没有重复数值，而二分查找的目的就是找到符合条件的下标。

比如想在有序数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] 中找到元素5的index，该如何写python代码呢：

python
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            return mid
    return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")

3 左边界 vs 右边界，查找相等的元素

当有序数组中存在重复值，即是由多个元素可以满足条件，返回哪一个下标更合适呢？

比如 arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]， 找数值5，那么左边界index是4，右边界index是6。

如果有序数组中有重复值，并且你想找到左边界的下标，你可以在二分查找的基础上，做一些改变来实现这个功能。

下面的代码展示了左边界和右边界的代码：

python
def binary_search_leftright(arr, x):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            result = mid  # 记录符合条件的下标
            # high = mid - 1  # 在区间 [low, mid-1] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往左找. 即找左边界。
            low = mid + 1  # 在区间 [mid+1, high] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往右找. 即找右边界。
    return result
arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")

4 难度升级，找到 x<6 的右边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x<6，且x是右边界元素：

python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1  # 继续在[mid+1, high]中查找，因为想找右边界
        else:
            high = mid  # 为什么不是mid-1呢?
    if arr[high] >= x:
        return high - 1
    else:
        return high
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 6
result = binary_search_right(arr, x)
print(result)

函数返回 high - 1 或者返回high。

• 如果将条件改为while low <= high呢，这样不可以吗？

如果你将循环的条件改为 while low <= high，在数组中查找小于目标值的右边界的时候是会有问题的。

当low==high时，如果arr[high] >= x 那么最终返回值就是high -1,而实际上并不是小于目标值的右边界。

因此，在二分查找中查找右边界时，循环条件应该是 low < high.

这样当循环结束时，high指向的就是第一个大于等于目标值的位置，而high - 1就是小于目标值的右边界

所以，在二分查找中查找右边界时，循环条件应该是 low < high 而非 low <= high,这是为了确保查找的正确性

除此之外，还可能发生死循环。

• 那为什么是high = mid ，而不是high = mid -1？

在查找小于目标值的右边界时，如果循环条件是 low < high, 当 arr[mid] >= x 时,如果 high = mid -1 会使得 high 不满足循环条件,从而导致循环终止，而不是移动到小于目标值的右边界。

而赋值high = mid会使得high = mid或者 high =

mid-1,这样high总是满足循环条件且正确地找到了第一个大于等于目标值的位置,而high-1就是小于目标值的右边界。

所以如果你想在查找小于目标值的右边界时，应该让 high = mid。这样可以保证查找的正确性。

5 找到 x>5 的左边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x>5，且x是左边界元素：

python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid - 1
    return low
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
print(result)

或者：

python
def binary_search_left(arr, x):
    low = 0
    high = len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid 
    return low

6 总结模板

当使用 "while low <= high" 时，要想结束循环，就需要更严格的判断，从而就不需要再单独对low 和high 进行特判。

如果要查找左边界（x>5的左边界）：

python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x: # 如果是x>=5，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return low

如果要查找右边界（x<6的右边界）：

python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: # 如果是x<=6，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return high