LeetCode二分專題
二分
二分模板
兩個模板：1.最大值最小模板一，2.最小值最大用模板二
單調性、兩段性的性質
版本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;
}
版本2：二分紅色端點是答案，最小值最大
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;
}
模板2要+1後再下取整
二分最後l和r相等
模板小結：
69. x 的平方根
check性質：t的平方<=x
找最小值最大，模板2
注意精度：long long mid = (long long )(l + (long long ) r + 1) >> 1;
class Solution {
public:
bool check(long long mid,int x){
return mid*mid <= x;
}
int mySqrt(int x) {
int l = 0,r = x;
while (l < r){
long long mid = (long long )(l + (long long ) r + 1) >> 1;
if(check(mid,x)) l = mid;
else r = mid - 1;
}
return l;
}
};
35. 搜索插入位置
check性質：t>=x，即第一個比x大或等的位置
最大值最小，模板1
class Solution {
public:
bool check(int mid,int x){
return mid >= x;
}
int searchInsert(vector<int>& nums, int target) {
if(nums.size() == 0 || nums.back() < target) return nums.size();
int l = 0,r = nums.size()-1;
while(l<r){
long long mid = (long long )(l + r )>>1;
if(check(nums[mid],target)) r = mid;
else l = mid + 1;
}
return l;
}
};
34. 在排序數組中查找元素的第一個和最後一個位置
兩個性質
1.check1：t>=x，找大於等於8的第一個位置，最大值最小，模板1
2.check2：t<=x，找小於等於8的最後1個位置，最小值最大，模板2
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) return {-1,-1};
int l = 0,r = nums.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[l] != target) return {-1,-1};
int start = 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 {start, l};
}
};
74. 搜索二維矩陣
最大值最小
或者最小值最大，找到目標即可
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;
}
};
153. 尋找旋轉排序數組中的最小值
check性質，nums[mid] <= nums.back() ，且找最大(右半段)滿足的最小下標
或者 nums[mid] < nums[0]，且找最小值最大
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size() == 0) return 0;
int l = 0,r = nums.size()-1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
return nums[r];
}
};
33. 搜索旋轉排序數組
思路，按153思路，先找最小值，分成兩段；然後按74題思路(最大值最小,且>=target)
兩次二分，注意r–後的邊界
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size() == 0) return -1;
int l = 0,r = nums.size()-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 = nums.size()-1;
else l = 0,r--;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(target == nums[l]) return l; //這裡要用l 否則之前r-- r可能是-1
return -1;
}
};
278. 第一個錯誤的版本
這道題給了check函數，兩段，第一個出錯的版本只需要找最大值最小
注意溢出 long long mid = (long long )(l + r >> 1);
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
long long l = 1 ,r = n;
while(l < r){
long long mid = (long long )(l + r >> 1);
if(isBadVersion(mid) == true) r = mid;
else l = mid + 1;
}
return r;
}
};
162. 尋找峰值
難度中等190 返回任何一個峰值所在位置即可。
方法1：線性掃描一遍
方法2：二分，比較mid 和 mid+1 如果mid+1的值比mid值大與等於那麼mid+1後肯定有峰值，如果mid比mid+1小說明左邊或者mid一定存在峰值
邊界不需要判，分析：while循環里mid不會等於最後1個點，因為當mid=最後1個點，說明l=r都等於最後1個點，那麼就退出循環了
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0 , r = nums.size()-1;
while( l < r){
int mid = l + r >> 1;
if(nums[mid] < nums[mid+1]) l = mid + 1;
else r = mid;
}
return l;
}
};
287. 尋找重複數
只能使用額外的 O(1) 的空間。
時間複雜度小於 O(n^2) 。
二分答案，二分這個數值，O(N)遍歷一遍數組統計在Lmid區間內的數的個數，如果個數比區間大小大那麼說明有一個重複，重複的數就在這個Lmid閉區間中，讓r=mid，否則在左區間(不包含mid)讓L=mid+1
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1;
int l = 1, r = n;
while( l < r){ //二分答案 二分這個數是多少
int mid = l + r >> 1;
int cnt = 0;
for(int i=0;i < nums.size();i++){
if(nums[i] >= l && nums[i] <= mid) cnt++;
}
if(cnt > mid - l + 1) r = mid;
else l = mid + 1;
}
return r;
}
};
275. H指數 II
滿足單調性，二分
最小值最大；l最小為0，r最大為n = size個
h滿足，h-1也一定滿足，可以把區間分成兩部分，前一部分紅色一定滿足，綠色不滿足，所以就是找最小值最大
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size() - 1;
int l = 0, r = citations.size();
while(l < r){
int mid = (l + r + 1) >> 1;
if(citations[n - mid + 1] >= mid) l = mid;
else r = mid - 1;
}
return l;
}
};
