二分查找
二分法是非常重要的基础算法，做题时注意边界的处理和循环不变量。
时间复杂度：O(logn)
基础模板：左闭右闭区间
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) /2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
}
return -1;
}
}
|
闭区间写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
}
|
左闭右开区间写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
return left;
}
}
|
开区间写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int search(int[] nums, int target) {
int left = -1, right = nums.length;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid;
else
right = mid;
}
return right;
}
}
|
二分查找的四种情况
1
2
3
4
5
6
7
8
9
10
11
| 1. >=：第一个大于等于target的下标
search(int[] nums, int target)
2. >：第一个大于target的下标：可以转换为`第一个大于等于 x+1 的下标`
search(int[] nums, int target+1)
3. <：最后一个小于target的下标：可以转换为`第一个大于等于target的下标` 的`左边位置`
search(int[] nums, int target)-1;
4. <=：最后一个小于等于target的下标：可以转换为`第一个大于等于 target+1 的下标` 的 `左边位置`
search(int[] nums, int target+1) - 1;
|
相关题目
思路
这道题就是在二分查找的基础上，增加了边界的思考，在二分查找结束后恰好可以把数组分为两部分：left左边的部分和right右边的部分，而且left左边的部分全部小于target，并以right结尾；right右边的部分全部大于等于target，并以left为首。所以最终答案一定在left的位置。
思路
两次搜索分别搜索最左出现的位置和最右出现的位置
思路
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素mid平方与 x的大小关系，并通过比较的结果调整上下界的范围。
思路
和69类似
二维二分
需要一定思考的二分
https://mp.weixin.qq.com/s/EjL65QmfX20xhhd-wKlgSg
部分问题不能直接套用模板
什么问题可以运用二分搜索算法技巧？
首先，你要从题目中抽象出一个自变量x,一个关于x的函数f(x),以及一个目标值target。同时，x,f(x),target还要满足以下条件：
1、f(x)必须是在x上的单调函数（单调增单调减都可以)。
2、题目是让你计算满足约束条件f(x)==target时的x的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
int f(int x){
}
int solution ( int[] nums, int target){
if (nums.length = 0) return -1;
int left =...
int right =...+1;
while (left<right){
int mid left(right-left) / 2;
if（f(mid) == target){
}else if (f(mid) < target) {
}else if (f(mid) > target) {
}
}
return left;
}
|
具体来说，想要用二分搜索算法解决问题，分为以下几步：
1、确定x,f(x),target分别是什么，并写出函数f的代码。
2、找到x的取值范围作为二分搜索的搜索区间，初始化left和right变量。
3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。
思路
二分找需要刷题数目a， 设已经刷了多少题为x，再二分找符合 < a + x - 1 与 > a + x + 1 的人数，根据题目要求比较即可。
思路
每一个零都是由一对 2 和 5 相乘得到的，在阶乘中，因子 2 的数量总是比因子 5 多，所以只需要计算因子 5 的数量就可以得到阶乘末尾零的数量。
进阶
二分的本质是「二段性」而非「单调性」，而经过下面的题，进一步发现「二段性」还能继续细分，不仅仅只有满
01 特性（满足/不满足）的「二段性」可以使用二分，满足 1? 特性（一定满足/不一定满足）也可以二分。