思路
首先一个区间分为两个,然后将答案确定在某个区间中,删掉另一个区间,这样每次就可以将答案范围缩小一半。
70% 满足单调性
95% 存在两段性
二分的流程
- 确定二分的边界
- 编写二分的代码框架
- 设计一个 check
- 判断一下区间如何更新
- 如果更新方式是 l=mid, r = mid - 1,使用模版二,在算 mid 的时候加 1
模版一
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是 r = mid 或者 l = mid + 1;,计算 mid 时不需要加 1。
C++ 代码模板:
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;
}
模版二
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是 r = mid - 1 或者 l = mid;,此时为了防止死循环,计算 mid 时需要加 1。
C++ 代码模板:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
相关题目列表
使用模版二,原因是所求的 mid 符合的条件是 mid*mid <= x 的时候,划分的区间是[l, mid - 1]和[mid, r],落到了后一个区间中。
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x;
while (l < r)
{
long long mid = l + r + 1ll >> 1;
if (mid <= x / mid ) l = mid;
else r = mid - 1;
}
return l;
}
};
使用模版一,nums[mid] >= target 所得的 mid 是要取的,所以划分为[l, mid]
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
两个模版的使用
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l = 0,r = nums.size();
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(l == nums.size() || nums[l] != target) return {-1,-1};
int left = l;
l = 0,r = nums.size()-1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
return {left,l};
}
};
- 33 Search in Rotated Sorted Array
/*
* @lc app=leetcode id=33 lang=cpp
*
* [33] Search in Rotated Sorted Array
*/
// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())
return -1;
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = (l + r) /2;
if (nums[mid] >= target && ((nums[mid] <= nums[r] )||(target >= nums[l])))
{
r = mid;
}
else if (nums[mid] < target && target >= nums[l] && nums[mid] < nums[l])
{
r = mid - 1;
}else{
l = mid+1;
}
}
return nums[l] == target ? l : -1;
}
};
// @lc code=end
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于