数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。输入：
每个测试案例包括两行：
第一行有1个整数n，表示数组的大小。1<=n <= 10^6。
第二行有n个整数，表示数组元素，每个元素均为int。
第三行有1个整数m，表示接下来有m次查询。1<=m<=10^3。
下面有m行，每行有一个整数k，表示要查询的数。
输出：
对应每个测试案例，有m行输出，每行1整数，表示数组中该数字出现的次数。
样例输入：
8
1 2 3 3 3 3 4 5
1
3
样例输出：
4
思想：使用二分法找到具体数字的位置，然后需要前后扫描来确定数字的个数~^_^
代码AC：
[cpp]
// 用2分法！！ ^_^
#include <stdio.h>
#include <stdlib.h>
int main()
{
long int n, i, cou, mid, low, high;
int m, *num, k;
while( scanf( "%ld", &n ) != EOF )
{
num = ( int* )malloc( sizeof( int ) * n );
for( i = 0; i < n; i++ )
{
scanf("%d", &num[i]);
}
scanf("%d", &m);
while( m-- )
{
scanf("%d", &k);
low = 0;
high = n - 1;
while( low <= high )
{
mid = ( low + high ) / 2;
if( k == num[mid] )
{
break;
}
else if( k > num[mid] )
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
cou = 0;
i = mid;
while( i < n )
{
if( num[i] == k )
{
cou++;
i++;
}
else
{
break;
}
}
i = mid - 1;
while( i >= 0 )
{
if( num[i] == k )
{
cou++;
i--;
}
else
{
break;
}
}
printf("%d\n", cou);
}
}
return 0;
}
补充：软件开发 , C++ ,
