剑指offer编程题—数字在排序数组中出现的次数

题目描述
统计一个数字在排序数组中出现的次数。

解题思路1
暴力循环

//暴力循环遍历
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int res=0;
        int len=data.size();
        for(int i=0;i<len;++i){
            if(data[i]==k) ++res;
        }
        return res;
    }
};

解题思路2
借用C++ STL中的算法equal_range()

//C++ equel_range(STL equal_range)二分查找算法
/*equal_range()可以找出有序序列中所有和给定元素相等的元素。equal_range()有三个
形参。前两个表示指定序列的两个正向迭代器，第三个参数是要查找的元素。
返回结果是一个pair对象，包含两个正向迭代器成员，first指向不小于第三个参数的元素，
second指向大于第三个参数的第一个元素。first和second也可以通过单独调用lower_bound()
和upper_bound()得到。
最后得到的匹配项范围是：[pair.first,pair.second)
也就是equal_range()找到的下边界就是指向要查找元素的第一个匹配项，上边界指向查找元素的最后一个匹配项的下一位。
*/
class Solution1 {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto resultPair = equal_range(data.begin(), data.end(),k);
       // cout<<*resultPair.first<<" "<<*resultPair.second<<endl; //输出5 6
        return resultPair.second - resultPair.first;
    }
};

解题思路3
自己实现二分查找算法，和思路2的效果是差不多的。不过要注意的细节多一些。

//二分查找的思想，找到给定数字k在有序序列中的做下标和右下标，两个下标的差+1就是k的个数
class Solution2 {
public:
    int rightposition(vector<int> data ,int k){
        int l=0;
        int r=data.size()-1;
        int mid;
        if(r<0 || data[l]>k) return -2; //注意为什么返回-2
        if(data[r]==k) return r;
        while((l+1)<r){
            mid=(l+r)>>1;
            if(data[mid]<=k) l=mid; //注意这里不能用if(data[mid]>=k) r=mid
            else r=mid;
        }
        return data[l]==k? l:-2;
    }
    int leftposition(vector<int> data ,int k){
        int l=0;
        int r=data.size()-1;
        int mid;
        if(r<0 || data[r]<k) return -1; //注意为什么返回-1
        if(data[l]==k) return l;
        while((l+1)<r){
            mid=(l+r)>>1;
            if(data[mid]>=k) r=mid; //注意这里不能用if(data[mid]<=k) l=mid。
            else l=mid;
        }
        return data[r]==k? r:-1;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int left=leftposition(data,k);
        int right=rightposition(data,k);
        return right-left+1; //注意为什么要+1
    }
};