有序数组中找出给定数字的出现次数

问题：

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

解答：

使用二分查找的方法分别找出给定数字的开始位置minIndex和结束位置maxIndex，最坏情况下时间复杂度为O(logn)。

简单代码如下：

/*
二分搜索
2.找 |最大| 下标i使得X[i] = V
  返回 i 或者-1
*/
int BinarySearch_Max(const int* X,int N,int V)
{
    if(X==NULL) return -1;
    int L=0,U=N-1,M;
    while(L+1 < U)
    {
        M = L+((U-L)>>1);
        if(X[M] <= V) L = M;
        else U = M;
    }
    if(X[U] == V) return U;
    if(X[L] == V) return L;
    return -1;
}
/*
二分搜索
2.找 |最小| 下标i使得X[i] = V
  返回 i 或者-1
*/
int BinarySearch_Min(const int* X,int N,int V)
{
    if(X==NULL) return -1;
    int L=0,U=N-1,M;
    while(L+1 < U)
    {
        M = L+((U-L)>>1);
        if(X[M] >= V) U = M;
        else L = M;
    }
    if(X[L] == V) return L;
    if(X[U] == V) return U;
    return -1;
}

/*
在排序数组中，找出给定数字的出现次数,如：
[ 1, 2, 2, 2, 3 ]
中2的出现次数是3次
*/
int Count(int *X, int N, int V)
{
    int minIndex = BinarySearch_Min(X,N,V);
    int maxIndex = BinarySearch_Max(X,N,V);
    cout<<"minIndex = "<<minIndex<<",maxIndex = "<<maxIndex<<endl;
    return maxIndex-minIndex+1;
}

简单测试代码：

    const int N = 5;
    int X[N] = {1,2,2,2,3};
    int C = Count(X,N,2);
    cout<<"Count = "<<C<<endl;