算法思想-二分查找
二分查找应用场景:寻找一个数、寻找满足条件的某个区间的左侧边界、寻找满足条件的某个区间的右侧边界
建议学习:二分查找详解
二分查找的基本框架
int binarySearch(vector<int> nums, int target){
int lo=..., hi=...;
while(...){
int mid = lo + (hi - lo) / 2;
if(nums[mid] == target)
...;
else if(nums[mid] > target)
hi = ;
else if(nums[mid] < target)
lo = ;
}
return ...;
}
在递增数组中寻找一个数(找出index,使得nums[index] == target)
int binarySearch(vector<int> nums, int target){
int lo=0, hi=nums.size()-1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
hi = mid - 1;
else if(nums[mid] < target)
lo = mid + 1;
}
return -1;
}
在递增数组中寻找满足条件的的区间的左侧边界(找出最小的index使得nums[index] >= target)
int binarySearch(vector<int> nums, int target){
int lo=0, hi=nums.size()-1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(nums[mid] >= target)
hi = mid - 1;
else if(nums[mid] < target)
lo = mid + 1;
}
if(lo >= nums.size())
return -1;
return lo;
}
在递增数组中寻找满足条件的区间的右侧边界(找出最大的index使得nums[index] <= target)
int binarySearch(vector<int> nums, int target){
int lo=0, hi=nums.size()-1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(nums[mid] <= target)
lo = mid + 1;
else if(nums[mid] > target)
hi = mid - 1;
}
if(hi < 0)
return -1;
return hi;
}
二分查找相关题目:
求开方
求满足条件y*y<x的最大的x
class Solution {
public:
int mySqrt(int x) {
if(x < 2)
return x;
long long lo = 0, hi = x;
while(lo <= hi){
long long mid = lo + (hi - lo) / 2;
if(mid * mid <= x)
lo = mid + 1;
else if(mid * mid > x)
hi = mid - 1;
}
return hi;
}
};
大于给定元素的最小元素
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int lo = 0, hi = letters.size()-1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(letters[mid] > target)
hi = mid - 1;
else if(letters[mid] <= target)
lo = mid + 1;
}
if(lo == letters.size())
return letters[0];
return letters[lo];
}
};
有序数组的 Single Element
二分搜索,通过两个数中的第一个数的index的奇偶判断single element在这个数的哪一边
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = nums.size()-1;
if(nums.size() == 1)
return nums[0];
while(lo <= hi){
int mid = (lo + hi) / 2;
if((mid == 0 && nums[mid] != nums[mid+1]) || (mid == nums.size()-1 && nums[mid] != nums[mid-1]) || (nums[mid-1] != nums[mid] && nums[mid+1] != nums[mid]))
return nums[mid];
if(mid > 0 && nums[mid-1] == nums[mid])
mid -= 1;
if(mid % 2 == 0)
lo = mid + 2;
else
hi = mid - 1;
}
return lo;
}
};
第一个错误的版本
class Solution {
public:
int firstBadVersion(int n) {
if(n == 1)
return 1;
int lo = 1, hi = n;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(isBadVersion(mid))
hi = mid - 1;
else
lo = mid + 1;
}
if(lo > n)
return n;
if(hi < 1)
return 1;
return lo;
}
};
旋转数组的最小数字
class Solution {
public:
int findMin(vector<int>& nums) {
return findMinHelper(nums, 0, nums.size()-1);
}
int findMinHelper(vector<int>& nums, int left, int right){
if(right == left)
return nums[left];
if(right == left + 1)
return min(nums[left], nums[right]);
if(nums[left] < nums[right])
return nums[left];
int mid = (left + right) / 2;
return min(findMinHelper(nums, left, mid), findMinHelper(nums, mid, right));
}
};
查找区间
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans(2, -1);
if(nums.size() == 0)
return ans;
int lo, hi;
lo = 0;
hi = nums.size() - 1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(nums[mid] >= target)
hi = mid - 1;
else if(nums[mid] < target)
lo = mid + 1;
}
if(lo != nums.size() && nums[lo] == target)
ans[0] = lo;
lo = 0;
hi = nums.size() - 1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(nums[mid] > target)
hi = mid - 1;
else if(nums[mid] <= target)
lo = mid + 1;
}
if(hi != -1 && nums[hi] == target)
ans[1] = hi;
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)