每日一道算法题：微软面试题：在排序数组中，找出给定数字出现的次数

题目：在排序数组中，找出给定数字出现的次数

解题思路：看完题目，想到的是先找出这个给定数字，在依次沿着这个数字在数组中的位置向前和向后继续遍历，分别记录下向后找到与这个给定数字不一样的数字前一位的下标a和向前找到与这个给定数字不一样的数字后一位的下标b，用a-b就是这个给定数字在数组中的长度，即出现的次数。那第一步怎样找到这个数字呢？既然数组是已经排好序的，用二分查找法平均速度会快些，代码如下：

#include <iostream>
using namespace std;

int count_num = 0;

void count_key(int arr[], int start, int end, int key){
    int middle = (start + end)/2;
    if (start > end){
        return ;
    }
    if (arr[middle] == key){
        count_num++;
        count_key(arr, start, middle-1, key);
        count_key(arr, middle+1, end, key);
    }
    else if(arr[middle] < key){
        count_key(arr, middle+1, end, key);
    }
    else{
        count_key(arr, start, middle-1, key);
    }
}

int main(){
    int arr[] = {1,2,2,2,3};
    count_key(arr, 0, 4, 2);
    cout << count_num << endl;
    system("pause");
    return 0;
}