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