作者： | 来源：互联网 | 2023-10-12 04:22
704.BinarySearch 1.使用start+1<end，这样保证最后剩两个数2.midstart+(end-start)2，这样避免接近ma
704. Binary Search
1.使用start+1
2.mid = start + (end - start)/2，这样避免接近max-int导致的溢出
3.start、end直接等于mid
4.最后比较两个位置
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())
return -1;
int start = 0;
int end = nums.size() - 1;
int mid;
while(start + 1 < end){
mid = start + (end - start)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid] < target)
start = mid;
else
end = mid;
}
if(nums[start] == target)
return start;
if(nums[end] == target)
return end;
return -1;
}
};
35. Search Insert Position
从左找第一个大于等于的，从右找第一个小于等于的
注意：分别针对找不到第一个在最后返回的值不同，从左返回的是最后一个位置，从右返回的是第一个位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty())
return -1;
for(int i = 0;i ){
if(nums[i] >= target)
return i;
}
return nums.size();
}
};
278. First Bad Version
第一个出错的之后都是出错的，实质上就是找第一个出错的
需要注意的是：第一个出错的值使用isBadVersion访问的时候返回的是true，不是false
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
if(n <= 0)
return -1;
int start = 1;
int end = n;
int mid;
while(start + 1 < end){
int mid = start + (end - start)/2;
if(isBadVersion(mid))
end = mid;
else
start = mid;
}
if(isBadVersion(start))
return start;
if(isBadVersion(end))
return end;
return -1;
}
};
京公网安备 11010802041100号