题解 | #二分查找-II#

二分查找，最开始做的时候遇到的一个坑。
按照常规解法使用left与right来标志查找位置，当left与right相等时退出查找。查找结点的位置为left+(right-left)/2，当left+(right-left)/2>target时，说明要查找的值在数轴左侧，要使right左移，反之当left+(right-left)/2<target时，说明要查找的值在数轴右侧，要使left右移。这里移动right与left时有一点问题，最初设想的比较简单，直接使left=left+(right-left)/2，使right=right-(right-left)/2，但是运行时出现个别输入不通过的情况，调试后发现这样移动left与right容易使查找循环进入死循环，因为这里的除运算是不做特殊处理直接去尾的，当找不到时就会出现(right-left)/2=0，从而left与right每次循环都不改变。而正确的移动left与right的方法时left=left+(right-left)/2+1，right=left+(right-left)/2-1，即不直接将中点赋值给left或right，而是赋于其中点的相邻点，这样就避免了除法截断导致的死循环。
这个问题解决后，还有一个问题是数组中存在重复元素，题目要求返回下标最小的结果，所以需要在后面加一个循环来寻找最小下标，这个问题不大。
源码如下。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        if(nums.size() == 0){
            return -1;
        }
        int right = nums.size() - 1;
        int left = 0;
        int index = 0;
        while(true){
            if(nums.at(left + (right - left)/2) == target){
                break;
            }
            if(nums.at(left + (right - left)/2) > target){
                right = left + (right - left)/2 - 1;

            }
            else if(nums.at(left + (right - left)/2) < target){
                left = left + (right - left)/2 + 1;
            }
            if(left == right || right < 0 || left >= nums.size()){
                break;
            }
        }
        if(right < 0 || left >= nums.size() || target != nums.at(left + (right - left)/2)){
            return -1;
        }
        else{
            index = left + (right - left)/2;
            while(index != 0 && nums.at(index - 1) == target){
                index--;
            }
            return index;
        }
    }
};