ABOUT

只做题，想思路

二分法

思路：两端的平均数跟要找的值对比，小了就缩小左边区间，大了就缩小右边区间，然后再次求两端的平均数，小了就缩小左边区间，大了就缩小右边区间，最终到达循环结束

1. 对比加缩小区间，写法很简单

if (nums[mid] > target){
                right = mid;
            }
            else if (nums[mid] < target){
                left = mid;
            }
            else if (target == nums[mid]){
                return mid;
            }

2. 结束条件呢？

while(left <= right)
or 
while(left < right)

3. 假设第一种结束条件

while(left <= right) {//一定会存在一种情况就是左右区间取了相同值，这个区间是左闭右闭的
if (nums[mid] > target){
                right = mid;
            }
            else if (nums[mid] < target){
                left = mid;
            }
            else if (target == nums[mid]){
                return mid;
            }
      mid = (left + right) / 2;
//考虑target在最右边，这个写法有问题
//考虑target在最左边，这个写法感觉没有什么问题，但是它循环了三次
}

当我们发现给left = mid; 改成left = mid + 1;最右边的情况解决了，但是最左边的情况还是循环三次；那我们给它right = mid;改成right = mid - 1;循环次数少了一次

why?
你只要画一下图，你就会发现其实mid所指向的那个数根本没有比的必要，所以left = mid + 1;可以，我刚刚说的target就算在最左边其实也可以比到，所以left可以加一；

减一呢？是否是我上面说的减一是为了循环次数少了一次？NONONO，这个减一非常有必要的加上去，不然就会出现死循环，比如target是在0到1之间的数，left跟right最终只会等于1，而无法返回正确结果，虽然我们知道死循环就是无解，就应该返回-1。

所以代码的最终样子是这样的

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (0 == nums.size())
            return -1;
        int left = 0;
        int right = nums.size() - 1;
        int mid = (left + right) / 2;

        if (nums[left] > target)
            return -1;
        if (nums[right] < target)
            return -1;
        if (nums[left] == target)
            return left;
        if (nums[right] == target)
            return right;
        //这四句是为了提高效率
        while(left <= right){
            if (nums[mid] > target){
                right = mid - 1;
            }
            else if (nums[mid] < target){
                left = mid + 1;
            }
            else if (target == nums[mid]){
                return mid;
            }
            mid = (left + right) / 2;
        }
        return -1;
    }
};

4. 第二种呢？

while(left < right)

经过上面的思考，我们发现不会出现死循环了，因为left < right，所以我们也不需要right = mid -1;

所以最终代码为：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (0 == nums.size())
            return -1;
        int left = 0;
        int right = nums.size() - 1;
        int mid = (left + right) / 2;
        if (nums[left] > target)
            return -1;
        if (nums[right] < target)
            return -1;
        if (nums[left] == target)
            return left;
        if (nums[right] == target)
            return right;
        while(left < right){
            if (nums[mid] > target){
                right = mid;
            }
            else if (nums[mid] < target){
                left = mid + 1;
            }
            else if (target == nums[mid]){
                return mid;
            }
            mid = (left + right) / 2;
        }
        return -1;
    }
};