[sword finger offer] interview question 53-i: find the number 1 in the sorted array -- three templates for binary search

Method 1 ： Binary search left and right boundaries

Reference resources labuladong Three templates of binary search , Search for target The left and right borders of .
You can also find the leftmost , Then find the same number after linear , But behind it is O(n) Complexity , If the same elements follow , There is no O(logn) fast .
Reference link ：
https://mp.weixin.qq.com/s/M1KfTfNlu4OCK8i9PSAmug

Left closed right open and left closed right closed code ：

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;
    }
};