微软面试题 -- 在排序数组中，找出给定数字的出现次数
在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

----------------------------------
网上一位仁兄写了如下解法：

int cnt(int a[], int v, int n){   int mid, b = 0, e = n-1;   int low, high;   while(b < e - 1)   {      mid = b + (e-b)/2;      if(a[mid] >= v)          e = mid;      else          b = mid;   }   if(a[b] == v)      low = b;   else if(a[e] == v)      low = e;   else      return 0;    b = 0;   e = n-1;   while(b < e -1)   {      mid = b +(e-b)/2;      if(a[mid] <= v)          b = mid;      else          e = mid;    }   if (a[e] == v)      high = e;   else if(a[b] == v)      high = b;   else       return 0;    return high - low + 1; }

个人认为可以先找到所指定的数，找到之后保留这个二分级数再向两端扩展可能会稍微快一点。

有几位仁兄说可以用hashtable来解决，但我感觉面试考的不是用hash