C++刷题之旅（1）

二分法基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

解答：

class Solution {
public:
    int search(vector& nums, int target) {
        int low = 0; 
        int high = nums.size()-1;    //定义target在左闭右闭的区间里，[low, high]，下标从0开始
        while (low <= high){      // 当left==right，区间[left, right]依然有效，所以用 <=  
            int mid = ((high - low) / 2 )+ low;         //取区间的中点,int是向下取整
            if(nums[mid] == target){        //当中点的数值值等于目标值时 直接返回中间值
                return mid;
            }
            else if(nums[mid] > target){
                high = mid -1;      //target在左区间，[low, mid - 1]
            }else{
                low = mid +1;       //target在右区间，[mid + 1, high]
            }
        }
        return -1;
    }
};

参考评论区大神的解析做如下补充：

首先这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。
有如下两点：
while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
if (nums[mid] > target) right 更新为 middle，因为当前nums[mid]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[midd]，因为nums[mid]取不到

// 版本二
class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid; // target 在左区间，在[left, middle)中
            } else if (nums[mid] < target) {
                left = mid + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[mid] == target
                return mid; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

解答：
本题也是一个二分法的应用，首先要注意的是由实例可知isBadVersion函数为true时，该版本为错误的版本，其次与上一题不同的是未引入vector容器，下标直接代表当前版本。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){      //第mid个版本为Bad   
                right = mid;   //则第一个Bad版本在[left, mid]之间， mid可能就是第一个，所以此处并不能用mid-1
            }else{      //第mid个版本不为Bad
                left = mid + 1;     //则第一个Bad版本在[mid+1, right]之间
            }
        }
        return left;
    }
};

解答：利用二分法在 O(log n)O(logn) 的时间内找到是否存在目标值，这题还多了个额外的条件，即如果不存在数组中的时候需要返回按顺序插入的位置，考虑这个插入的位置pos，它成立的条件为：nums[pos−1]

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target)
            {
                return mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid -1;
            }
        }
        // left > right的情形，数组中无目标值
        if(right < mid){		//表示最后一步从right = middle - 1分支跳出,也即nums[middle] > target，重新插入位置即为mid;
			return mid;
		}
        return mid + 1;		//表示nums[middle] < target,重新插入位置为middle+1;
    }
};