【剑指offer】面试题53-Ⅰ：在排序数组中查找数字1 —— 二分查找的三个模版

方法一：二分查找左右边界

参考labuladong的二分查找的三个模版，进行查找target的左右边界。
也可以找到最左边，然后线性找后面相同的数字，但是后面是O(n)的复杂度，如果后面都是相同的元素，就没有O(logn)快。
参考链接：
https://mp.weixin.qq.com/s/M1KfTfNlu4OCK8i9PSAmug

左闭右开以及左闭右闭的代码：

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

            // l=0;
            // r=nums.size();
            // while(l<r){
    
            // int mid=(l+r)>>1;
            // if(nums[mid]>target) r=mid;
            // else l=mid+1;
            // }
            // return l-1-left+1;
            int left = getFirstTarget( 0, nums.size() - 1 , target, nums);
            if( left == -1 )
                return 0;
            int right = getLastTarget( 0, nums.size() - 1 , target, nums);
            return right - left + 1;
    }

    int getFirstTarget( int left, int right, int target, vector<int>& nums )
    {
    
        while(left <= right)
        {
    
            int mid = left + ( right - left ) / 2;
            if( nums[mid] == target )
                right = mid - 1;
            else if( nums[mid] > target )   
                right = mid - 1;
            else if( nums[mid] < target )
                left = mid + 1;
        }
        if( left >= nums.size() || nums[left] != target )
            return -1;
        return left;
    }
    int getLastTarget( int left, int right,int target, vector<int>& nums )
    {
    
        while( left <= right )
        {
    
            int mid = ( left + right ) / 2;
            if( nums[mid] == target )
                left = mid + 1;
            else if( nums[mid] > target )   
                right = mid - 1;
            else if( nums[mid] < target )
                left = mid + 1;
        }
        if( right < 0 || nums[right] != target )
            return -1;
        return right;
    }
};