思路：
应该是用二分查找分别找到该数字第一次和最后一次出现的位置，相减即可。O(logn)
int findLeft(int a[], int n, int num)
{
int l = , r = n - ;
while(l <= r)
{
int m = l + (r - l) / ;
if(a[m] == num) //与普通二分查找的区别在等于这里
{
if(m == || a[m - ] != num) //如果这是第一个数字或者它前面的数字不是num那么这个位置就是第一个num出现的位置
return m;
else //否则num在左半部分
r = m - ;
}
else if(a[m] < num)
{
l = m + ;
}
else
{
r = m - ;
}
}
return -; //没找到
} int findRight(int a[], int n, int num)
{
int l = , r = n - ;
while(l <= r)
{
int m = l + (r - l) / ;
if(a[m] == num)
{
if(m == n - || a[m + ] != num) ////如果这是最后一个数字或者它后面的数字不是num那么这个位置就是最后一个num出现的位置
return m;
else //否则 最后一个num在右半部分
l = m + ;
}
else if(a[m] < num)
{
l = m + ;
}
else
{
r = m - ;
}
}
return -; //没找到
} int times(int a[], int n, int num)
{
if(a == NULL) return ;
int l = findLeft(a, n, num);
int r = findRight(a, n, num);
return (l == - || r == -) ? : r - l + ;
} int main()
{
int a[] = {,,,,,,,};
int ans = times(a, , ); return ;
}
最开始写的是用普通二分查找找到一个指定数字再左右扩展，O(N)不好。
//O(N)解法 不好
int appearTimes(int a[], int n, int num)
{
int l = ;
int r = n - ;
int pos = -; //找到的num的下标
while(l <= r) //二分查找 找到一个num
{
int m = l + (r - l) / ;
if(a[m] == num)
{
pos = m;
break;
}
else if(a[m] < num)
l = m + ;
else
r = m - ;
}
if(pos == -) //没有该数字
return ; l = r = pos;
while(l >= && a[l] == num) //找左边界
l--;
while(r < n && a[r] == num) //找右边界
r++; return r - l - ;
}