题解 | #二分#

二分

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int n = data.size();
        if(n == 0) return 0;
        int left = 0, right = n - 1;
        int start = lower_bound(data.begin(), data.end(), k) - data.begin();
        if(data[start] != k) return 0;
        int end = lower_bound(data.begin(), data.end(), k + 1) - data.begin();
        //cout << start << " " << end;
        return end - start;
    }
};

class Solution {
public:
    int helper(vector<int> data, int target){
        int n = data.size();
        int left = 0, right = n - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(data[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int n = data.size();
        if(n == 0) return 0;
        int left = 0, right = n - 1;
        int start = helper(data, k);
        if(data[start] != k) return 0;
        int end = helper(data, k + 1);
        if(data[end] == k) end ++;
        return end - start;
    }
};