// 题目：统计一个数字在排序数组中出现的次数。

//  比如：排序数组｛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;

}