二分查找

二分查找（Binary Search）是一种高效的搜索算法，适用于有序数组或有序列表。它通过不断地将搜索范围减半来查找目标元素，从而在O(log n)的时间复杂度内找到特定元素的位置。
在有序数组中找到中间位置的元素，与目标元素进行比较。如果中间元素等于目标元素，则搜索成功；如果中间元素大于目标元素，则在数组的左半部分继续进行二分查找；如果中间元素小于目标元素，则在数组的右半部分进行二分查找。通过不断重复这个过程，直到找到目标元素或搜索范围缩小到为空为止。

基本模板

找到大于等于target的第一个数（最左边）

nums = [1, 2, 4, 5, 5, 6], target = 5 -> l = 3

1
2
3
4
5
6
int l = 0, r = n;
while (l < r) {
    int m = l + (r-l)/2;
    if (nums[m] >= target) r = m;
    else l = m + 1;
}

找到大于target的第一个数

1
2
3
4
5
6
int l = 0, r = n;
while (l < r) {
    int m = l + (r-l)/2;
    if (nums[m] > target) r = m;
    else l = m + 1;
}

找到小于等于target的最后一个数（最右边）

nums = [1, 3, 3, 5, 7, 9], target = 5 -> l = 2

1
2
3
4
5
6
int l = -1, r = n-1;
while (l < r) {
    int m = l + (r-l+1)/2;
    if (nums[m] <= target) l = m;
    else r = m - 1;
}

找到小于target的最后一个数

nums = [1, 3, 3, 5, 7, 9], target = 5 -> l = 2

1
2
3
4
5
6
int l = -1, r = n-1;
while (l < r) {
    int m = l + (r-l+1)/2;
    if (nums[m] < target) l = m;
    else r = m - 1;
}

模板中可以diy的地方主要有两个：

  1. 首先是m = l + (r-l)/2和m = l + (r-l+1)/2
    • 如果是m = l + (r-l+1)/2的话，那么还需要修改l = m and r = m-1，否则无法结束循环
    • 两者的区别主要体现在，当到达临界值时，左式取m偏右一位，所以得到的是大于或者大于等于的第一个数；而右式取m偏左一位
  2. 还有就是是否取等号if (nums[m] < target)和if (nums[m] <= target)，是否需要大于等于或者小于等于

最小化最大值 或 最大化最小值 问题

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

与其他算法结合