二分查找

发表于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟
引言： 二分查找模板

两个二分查找模板

二分查找是比较重要的一个算法思想，这里使用两个二分法的模板来解释二分查找的细节问题。

目标：对于数组nums，要找到target的下标位置

模板一：边界外

看这个更清楚

二分模板如下：

1
2
3
4
5
6
7
8
9
10
// 1、初始条件需要卡在0和nums.length-1之外
int l = -1;
int r = nums.length;

whle(l + 1 != r){ // 2、循环条件
    int m = (l + r) / 2;
    if(condition) l = m; // 3-1、设置值别 l = m - 1 ，这样容易弄错
    else r = m; // 3-2、设置值别 l = m - 1 ，这样容易弄错
}
return r or l; // 4、按照条件与题意选择 l或是r返回

问题1：为什么边界条件要设置在数组的外边？

因为如果整个数组都<或>预期值target，我们的l与r边界就会出现问题

问题2：循环条件为什么是 l + 1 != r，我用l < r不行吗？

假设有三种情况：

1
2
3
4
... L R ... // 情况1：: L + 1 == R 成立，不会进入循环
... L X R ... // 情况2： L + 2 == R，进入循环，他的下一步就是情况1
... L X X R ... // 情况3：可以归类到情况2
...

如果我们的循环条件是l < r，对于情况1会进入循环，这是两种条件的区别。

现在我们求这道题：对于数组nums，要找到target的下标位置

由此我们可以快速的得出：

1
2
3
4
5
6
7
8
int l = -1;
int r = nums.length;
for(;l+1 != r;){
    int m = (l + r) / 2;
    if(nums[m] < target) l = m;
    else r = m;
}
return r;

此处我们的条件是nums[m] < target，我们的结果就会变成：

1
....lr....

l及其左边都是<target的数值；r及其右边都是>= target的数值，因此我们要求target的位置就应该选择返回r

同理，如果你的条件是<= target，那么就应该返回l

在思考到底要返回l还是r时，我们可以脑海构建一个 类似...lr...的图，结合条件，就可以立马反应我们该返回哪一个值了。

Exec：

35. 搜索插入位置

74. 搜索二维矩阵

34. 在排序数组中查找元素的第一个和最后一个位置

模板二：边界上

适合解决旋转有序数组的问题。

1
2
3
4
5
6
7
8
9
10
// 1、初始条件卡在边界
int l = 0;
int h = nums.length - 1;
for (; l <= h;) { // 2、循环条件就是 l <= r
    int mid = (h + l) / 2; // 3、找中间值
    if (nums[mid] == target) return mid; // 4、找到值就返回
    if (nums[mid] < target) l = mid + 1;
    else h = mid - 1;
}
return l;

Exec：

35. 搜索插入位置

33. 搜索旋转排序数组

153. 寻找旋转排序数组中的最小值