面试题38：数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。例如输入数组{1,2,3,3,3,3,4,5}和数字3，由于3在数组中出现了4次，因此输出4.

分析

看到排序数组，我们自然而然会想到二分法。但平常的二分法只能找到这个数字，并不能找出出现的次数，或者该数字的最左和最右边界。那么我们就需要改进一下：

假设数组是升序排列的，当我们用二分法找到这个数时，再继续用二分法去找它的左右边界，因此需要分别写两个函数。以找左边界为例，设现在有left，right和mid分别指向数组的最左，最右和中间数字，且中间数字恰好为我们要找的数字。这时候就在left和mid之间用二分法去找，假设mid2=left+(mid-left)/2；此时有如下几种情况：

• arr[mid2]==我们要找的数字，且arr[mid2-1]不等于我们要找的数字，则return mid2。否则继续在left和mid2之间找。
• arr[mid2]<我们要找的数字，则在mid2和mid之间找。
• arr[mid2]>我们要找的数字？？what？这是不可能滴！因为数组是升序排序的，且arr[mid]==我们要找的数字且mid>mid2.

综上，我们可以利用递归去找最左和最右的数字，将其下标相减就可以得到该数字出现的次数。

代码如下：

```template int _GetLeft(const vector& v,int left,int right,const T& k) { if(left==right) return right; int mid=left+(right-left)/2; if(v[mid]==k) return _GetLeft(v,left,mid,k); else return _GetLeft(v,mid+1,right,k); }

template int _GetRight(const vector& v,int left,int right,const T& k) { if(left==right) return left; if(left==right-1) { if(v[left]==k) return left; else return right; } int mid=left+(right-left)/2; if(v[mid]==k) return _GetRight(v,mid,right,k); else return _GetRight(v,left,mid-1,k); }

template int _NumberOfK(const vector& v,int left,int right,const T& k) { if(left>right) return 0; int mid=left+(right-left)/2; if(v[mid]>k) return _NumberOfK(v,left,mid-1,k); else if(v[mid]<k) return NumberOfK(v,mid+1,right,k); else { int r=GetRight(v,mid,right,k); int l=_GetLeft(v,left,mid,k); //cout<<l<<" "<<r<<endl; return r-l+1; } }

template int NumberOfK(const vector& v,const T& k) { return _NumberOfK(v,0,v.size()-1,k); } ```

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往