剑指offer37-数字在排序数组中出现的次数

题目描述

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

思路：

最简单的从头遍历

更优化的方案利用二分法。

我做的时候，一开始在while循环里面忘记mid=(begin+end)/2，导致运行时间超长进入死循环。粗心啊！！！

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //给你一个有序的数组，找到k出现的次数
        int len = data.size();
        if(len==0) return 0;
        int begin = 0;
        int end = len-1;
        int mid = (begin+end)/2;
        int count = 0;
        while(end>=begin){
            mid = (begin+end)/2;
            if(data[mid]==k){
                for(int i=begin;i<=end;i++){
                    if(data[i]==k)
                        count++;
                }
                break;
            }
            else if(data[mid]>k){
                end = mid-1;
            }
            else{
                begin = mid+1;
            }
        }
        return count;
    }
};