// 题目：统计一个数字在排序数组中出现的次数。
// 比如：排序数组｛1。2，3，3，3，3，4。5｝和数字3，因为3出现了4次。因此输出4
有一种最简单的算法，遍历。可是有比它效率更高的
先看遍历：
#include <stdio.h>
#include <assert.h> int num_time(int *arr, int len, int a)
{
int i = 0;
int count = 0;
assert(arr != NULL);
for (; i < len; ++i)
{
if (arr[i] == a)
count++;
}
return count;
} int main()
{
int arr[] = { 1, 2, 3, 3, 3, 3, 4, 5 };
int len = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", num_time(arr, len, 3));
return 0;
}
另一种利用二分查找：
#include <stdio.h> int GetFirstKey(int arr[], int left, int right, int len, int key)
{
int mid;
if (left > right)
{
return -1;
}
mid = left - (left - right) / 2;
if (key == arr[mid])
{
if ((mid > 0 && arr[mid - 1] != key) || mid == 0)
{
return mid;
}
else
{
right = mid - 1;
}
}
else if (arr[mid] < key)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
return GetFirstKey(arr, left, right, len, key);
} int GetLastKey(int arr[], int left, int right, int len, int key)
{
int mid;
if (left > right)
{
return -1;
}
mid = left - (left - right) / 2;
if (key == arr[mid])
{
if ((mid < len - 1 && arr[mid + 1] != key || mid == len - 1))
{
return mid;
}
else
{
left = mid + 1;
}
}
else if (arr[mid] < key)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
return GetLastKey(arr, left, right, len, key);
} int main()
{
int brr[] = { 1, 2, 3, 3, 3, 3, 4, 5};
int len = sizeof(brr) / sizeof(brr[0]);
int first = GetFirstKey(brr, 0, len - 1, len - 1, 3);
int last = GetLastKey(brr, 0, len - 1, len - 1, 3);
printf("%d\n", last - first + 1);
return 0;
}