二分查找基础专题——二分模板
二分查找基础
1.前言
以前总觉得得先把概念都过一遍完全理解了才能开始刷题，殊不知实践才是掌握知识的捷径，而不是背了忘忘了背。学知识本来就需要沉下心，一步一个脚印的走，否则在未来某个关键时刻会因当初的囫囵吞枣而受到惩罚。
所以别想那么多，直接开刷就是了，先从简单的二分查找开始。但是有一说一，二分思想虽简单，但是处理细节需格外小心，否则容易导致死循环。
2.概念核心
有序、折半查找、时间复杂度O(logN)
3.算法模板
通常我们的算法题都不会直接让我们用二分求某个数，都需要我们根据实际情况转换一下。
二分题目通常分为两种类型：
- 第一种是查找第一个满足条件的下标，即
00001111找第一个1的情况 - 第二种是查找最后一个满足条件的下标，即
11110000找最后一个1的情况
/*模板一（左边为0右边为1），查找第一个1，00001111
* check(mid)意思为找到'1'，此时mid可能是右边任何一个'1'，
* 即无法确定mid是否为第一个'1'，所以我们在向左边缩小范围时不能写成
* r=mid-1,要写成r=mid;
* 同理，else情况为没找到'1'，所以向右边缩小范围，因为mid肯定不满足条件，所以l=mid+1
*/
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
/*模板二（左边为1右边为0），查找最后一个1，11110000
* check(mid)意思为找到'1'，此时mid可能是左边任何一个'1'，
* 即无法确定mid是否为最后一个'1'，所以我们在向右边缩小范围时不能写成
* l=mid+1,要写成l=mid;
* 同理，else情况为没找到'1'，所以向左边缩小范围，因为mid肯定不满足条件，所以r=mid-1
*/
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; //加1避免死循环 eg:10
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
4.Leetcode二分基础题目
思路解析：
通常一个整数的平方根是一个无限不循环小数，依题意知要返回一个小于等于平方根的整数。换句话说，我们就只需要从小于等于平方根的整数中找到最大的那个整数，符合11110000找最后一个1的模型，即模板二。
最后注意下数据范围即可。
class Solution {
public:
int mySqrt(int x) {
long long l = 0, r = x;
while (l < r) {
long long mid = l + r + 1 >> 1;
if (mid * mid <= (long long)x) l = mid;
else r = mid - 1;
}
return l;
}
};
思路解析：
由题意知没有重复的元素，故模板一、模板二都可以，这里使用模板一。这里要特殊考虑一下数组为空，或者查找元素小于、大于所有数组元素的情况。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
if (len == 0) return 0;
if (nums[len - 1] < target) return len;
if (nums[0] > target) return 0;
int l = 0, r = len - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
思路解析：
这个思路很清晰，先使用模板一00001111查找第一个1；然后从找到的第一个1开始使用模板二11110000查找最后一个1。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int len = nums.size();
if (len == 0) return {-1, -1};
vector<int> vec;
int l = 0, r = len - 1, st = 0, ed = 0;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] == target) {
st = l;
int low = st, high = len - 1;
while (low < high) {
int mid = low + high + 1 >> 1;
if (nums[mid] > target) high = mid - 1;
else low = mid;
}
ed = low;
vec.push_back(st);
vec.push_back(ed);
} else {
vec.push_back(-1);
vec.push_back(-1);
}
return vec;
}
};
思路解析：
单纯的二分查找，使用模板一、模板二都可以。关键在于二维矩阵下标的表示。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 || matrix[0].size() == 0) return false;
int n = matrix.size();
int m = matrix[0].size();
int l = 0 ,r = n * m - 1;
while(l < r){
int mid = l + r >> 1;
if(matrix[mid/m][mid%m] >= target) r = mid;
else l = mid + 1;
}
if(matrix[r/m][r%m] == target) return true;
return false;
}
};
思路解析：
由题意知，旋转数组如图所示，要找最小值等价于00001111找第一个1。我们只要把判断条件设置为小于等于数组最后一个值，此时左边由图知是大于数组最后一个值的，设置为0，右边设置为1。
image
class Solution {
public:
int findMin(vector<int>& nums) {
int len = nums.size();
int l = 0, r = len - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
思路解析：
这道题是上一题的进阶版，我们可以按照上一题的思路，先通过二分查找找到旋转数组的最小值。然后对数组最后一个数与目标数进行比较，缩小范围。再进行一次二分查找。
class Solution {
public:
int search(vector<int>& nums, int target) {
int len = nums.size();
if (len == 0) return -1;
int l = 0, r = len - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
if (target <= nums.back()) r = len - 1;
else l = 0, r--;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return nums[l] == target ? l : -1;
}
};
思路解析：
这个一眼就能看出是00001111查找第一个1的模型，套模板就可以。
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l >> 1);
if (isBadVersion(mid)) r = mid;
else l = mid + 1;
}
return l;
}
};
5.总结
上面的题目也仅仅是刷一下二分查找的熟练度，下次分享会总结下【二分答案】的专题，那个面试可能问的比较多。
