题解 | #数字在升序数组中出现的次数#

二分法找边界

1、首先要明确划分的区间类型，是左闭右开还是左闭右闭

• 左闭右闭是while(left<=right),当left==right时还需要计算[left,right]
• 左闭右开是while(left<right),因为left==right时不需要计算[left,right)

2、找边界有4种情况

• 边界在区间左边(越界)
• 边界在区间右边(越界)
• 边界在区间里面但找不到目标值 : (1,3,3,5)找2
• 边界在区间里面能找到目标值 : (1,3,3,5)找3

3、做法

• 可以定义leftBorder=-2 来确认 目标值(6) 没左边界
• 同理定义rightBorder=-2 来确认 目标值(0) 没右边界
• 边界在区间内的可以通过data[mid]<=target中的等于情况找到右边界
• 边界在区间内的可以通过data[mid]>=target中的等于情况找到左边界

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //二分法首先要确定二分后是左闭右开，还是左闭右闭的情况，此处使用左闭右闭
        int leftBorder = getLeftBorder(data,k);
        int rightBorder= getRightBorder(data,k);
        
        if(rightBorder==-2||leftBorder==-2)return 0;
        return rightBorder-leftBorder-1;
    }
    int getLeftBorder(vector<int> data,int k){
        int leftBorder=-2;
        int left = 0,right =data.size()-1;
        while(left<=right){
            int mid =  left + ((right-left)>>1);
           // 当data[mid] == target的时候，更新right，这样才能得到target的左边界
            if(data[mid]>=k){
                right = mid -1;
                leftBorder=right;
            }else{
                left = mid+1;
            }
        }
        
        return leftBorder;
    }
    
    int getRightBorder(vector<int>data , int k){
        int rightBorder=-2;
        int left = 0,right =data.size()-1;
        while(left<=right){
            int mid  =left+((right-left)>>1);
           // 当data[mid] == target的时候，更新left，这样才能得到target的右边界
            if(data[mid]<=k){
                left=mid+1;
                rightBorder=left;
            }else{
                right=mid-1;
            }
        }
        return rightBorder;
    }
};