二分查找

概念

二分查找（Binary Search）是一种高效的搜索算法，适用于有序数组或有序列表。它通过不断地将搜索范围减半来查找目标元素，从而在O(log n)的时间复杂度内找到特定元素的位置。

基本思想是

在有序数组中找到中间位置的元素，与目标元素进行比较。如果中间元素等于目标元素，则搜索成功；如果中间元素大于目标元素，则在数组的左半部分继续进行二分查找；如果中间元素小于目标元素，则在数组的右半部分进行二分查找。通过不断重复这个过程，直到找到目标元素或搜索范围缩小到为空为止。

此外，二分查找也可以进行变种，例如找到大于/小于目标元素的最小/最大元素，或者找到目标元素的第一个/最后一个位置等。它在各种应用场景中都有广泛的应用，如在搜索引擎、数据库查询、游戏开发等领域中都能发挥重要作用。

基本模板

  • 找到大于等于target的第一个数
1
2
3
4
5
while (l < r) {
    int m = l + (r-l)/2;
    if (nums[m] < target) l = m + 1;
    else r = m;
}
  • 找到大于target的第一个数
1
2
3
4
5
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偏左一位
    • 有些题目只能取m偏右，例如：35. 搜索插入位置
  2. 还有if (nums[m] < target)和if (nums[m] <= target)
    • 这里主要考虑的是，当m的值取到相等时，你想往哪个方向进行偏移
    • 上面的例子中nums[m] >= target时，r = m，m就是向左偏移

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

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

与其他算法结合