Sword finger offer 53 - I. find the number I in the sorted array (improved bisection)

Binary search found one target, Then start counting on both sides

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    
        int l = 0;
        int r = nums.size() - 1;
        int pos = -1;

        while(l <= r){
    
            int mid = l + ((r - l) >> 1);
            if(nums[mid] == target){
    
                //  find 
                pos = mid;
                break;
            }else if(nums[mid] < target){
    
                l = mid + 1;
            }else{
    
                r = mid - 1;
            }
        }
        if(pos == -1){
    
            return 0;
        }
        int cnt = 1;
        int left = pos - 1;
        while(left >= 0 && nums[left] == target){
    
            cnt++;
            left--;
        }
        int right = pos + 1;
        while(right < nums.size() && nums[right] == target){
    
            cnt++;
            right++;
        }
        return cnt;
    }
};

We need to know , When $nums[mid]<target$ when ,$l$ Will move to the right , in other words ,$l$ It is impossible to cross any one of the arrays $target$ value . for the first time $mid$ Point to $target$ when , Do not exit search , It's going to continue the cycle , until $l==r$ Just quit .

because $l$ Will not cross any one $target$ value ,$r$ It is only possible to point to no greater than $target$ Value , The exit conditions we set are $l==r$, If... Exists in the array target, When you finally quit ,$l$ and $r$ It must point to the leftmost $target$

class Solution {
    
public:
    int search(vector<int>& nums, int target) {
    
        int l = 0;
        int r = nums.size() - 1;
        int cnt = 0;

        while(l < r){
    
            int mid = l + ((r - l) >> 1);
            if(nums[mid] >= target){
    
                //  here mid May point to target, Out of commission r = mid - 1 Cross current value 
                r = mid;
            }else{
    
            	//  At this time mid Less than target,l You can cross mid
                l = mid + 1;
            }
        }

        while(l < nums.size() && nums[l] == target){
    
            l++;
            cnt++;
        }
        return cnt;
    }
};