NC105 #二分查找-II#

二分搜索模板，然后下标前移。
注意：写成left + (right - left) / 2而不是(left + right) / 2可以避免溢出。

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