首页 > 代码库 > 剑指offer38

剑指offer38

这种方法没用迭代,而是使用了循环的方式

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        int First = getFirstofK(data,k);
        int Last = getLastofK(data,k);
        if(First == -1 || Last == -1)
            return 0;
        else
            return Last - First + 1;
    }
    int getFirstofK(vector<int> data,int k){
        int length = data.size();
        int begin = 0;
        int end = length - 1;
        while(begin <= end){
            int mid = (begin + end)/2;
            if(data[mid] == k){
                if(data[mid-1] != k)
                    return mid;
                else
                    end = mid - 1;
            }
            else if(data[mid] < k)
                begin = mid + 1;
            else
                end = mid - 1; 
        }
        return -1;
    }
    int getLastofK(vector<int> data,int k){
        int length = data.size();
        int begin = 0;
        int end = length - 1;
        while(begin <= end){
            int mid = (begin + end)/2;
            if(data[mid] == k){
                if(data[mid+1] != k)
                    return mid;
                else
                    begin = mid + 1;
            }
            else if(data[mid] < k)
                begin = mid + 1;
            else
                end = mid - 1; 
        }
        return -1;
    }
};

 

剑指offer38