二分法

二分的模板有许多种，下面列举一种：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 范围查询规律
* 初始化:
*   int left = 0;
*   int right = nums.length - 1;
* 循环条件
*   left <= right
* 右边取值
*   right = mid - 1
* 左边取值
*   left = mid + 1
* 查询条件
*   >= target值, 则 nums[mid] >= target时, 都减right = mid - 1
*   >  target值, 则 nums[mid] >  target时, 都减right = mid - 1
*   <= target值, 则 nums[mid] <= target时, 都加left = mid + 1
*   <  target值, 则 nums[mid] <  target时, 都加left = mid + 1
* 结果
*   求大于(含等于), 返回left
*   求小于(含等于), 返回right
* 核心思想: 要找某个值, 则查找时遇到该值时, 当前指针(例如right指针)要错过它, 让另外一个指针(left指针)跨过他(体现在left <= right中的=号), 则找到了
*/

二分查找的时间复杂度为 O(lg n)，在很多题目中都能使用这个技巧对题目进行简化。

比如在最长递增子序列中，可以使用二分将新的数插入到递增子序列中。

中等：911. 在线选举

由于此题的时间满足单调递增的性质，所以可以使用二分法来查询。

在做这道题的时候，需要找到第一个 <= target 的位置，我犯了两个错误。

  • 处理边界情况，但实际上不需要处理。
  • 当 nums[mid] <= target 时，我想的是令 right = mid - 1。理由是答案一定在左边，所以右边界要往左。这样想是错误的。

当我们要找第一个 <= target 的 index 时，我们应该想的是，mid 一定是满足条件的，所以答案在区间 [mid, right] 当中，自然而然要把左边界往右边移动。

这里容易想错，切记！

参考