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 -;
}
};