[微软面试题] 在排序数组中，找出给定数字的出现次数

找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3。

这道题只要二分不要写错就完全没问题。

这是网上某人给出的代码，利用递归版二分来查找数字：

#include <iostream>

using namespace std;

int cnt=0;

void countNum(int a[],int x,int start,int finish)
{
    int middle=(start+finish)/2;
    if(start>finish)
      return ;
    if(a[middle]==x)
    {
        cnt++;
        countNum(a,x,start,middle-1);
        countNum(a,x,middle+1,finish);
    }else if(a[middle]>x)
    {
        countNum(a,x,start,middle-1);
    }else
    {
       countNum(a,x,middle+1,finish);
    }
}
int main()
{
    int s[]={1,2,2,2,3};
    int start=0;
    countNum(s,2,start,4);
    cout<<cnt<<endl;
    getchar();
    return 0;
}

不过我觉得效率还能更好，我的方法是非递归版二分，找到数字向两边扩展，不需要继续二分：

#include<iostream>
using namespace std;

int num[5] = {1, 2, 2, 2, 3};

int search(int x)
{
	int i = 0, j = 5;
	int mid = (i+j) >> 1;
	while(num[mid] ^ x)
	{
		if(num[mid] > x)
			j = mid;
		else
			i = mid;
		mid = (i+j) >> 1;
	}
	int l = 0, lidx = mid-1;
	int r = 0, ridx = mid+1;
	while(lidx >= 0 && num[lidx--] == x)
		l++;
	while(ridx <= 4 && num[ridx++] == x)
		r++;
	return l + r + 1;
}

int main()
{
	printf("%d\n", search(2));
	getchar();
	return 0;
}