leetcode 704. Binary Search 、35. Search Insert Position 、278. First Bad Version

时间:2023-03-10 01:33:59
leetcode 704. Binary Search 、35. Search Insert Position 、278. First Bad Version

704. Binary Search

1.使用start+1 < end,这样保证最后剩两个数

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 -;
int start = ;
int end = nums.size() - ;
int mid;
while(start + < end){
mid = start + (end - start)/;
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 -;
}
};

35. Search Insert Position

从左找第一个大于等于的,从右找第一个小于等于的

注意:分别针对找不到第一个在最后返回的值不同,从左返回的是最后一个位置,从右返回的是第一个位置

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty())
return -;
for(int i = ;i < nums.size();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 <= )
return -;
int start = ;
int end = n;
int mid;
while(start + < end){
int mid = start + (end - start)/;
if(isBadVersion(mid))
end = mid;
else
start = mid;
}
if(isBadVersion(start))
return start;
if(isBadVersion(end))
return end;
return -;
}
};