学步园

问题描述：统计一个数字在排序数组中出现的次数。例如排序数组{1,3,4,4,4,4,4,6,7,9}，要查找数字4出现的次数，由于4在这个数组中出现了5次，所以输出5。

分析：看到是排序的数组，理所当然的想到用二分查找。然而需要查找的数字可能在数组中出现多次，所以在查找到第一个目标数字后，还需要对目标数字的左右两边进行顺序扫描，直到找到排序数组中第一个目标数字和最后一个目标数字。因为要查找的数字在长度为n的数组中可能出现n次，所以顺序扫描的时间复杂度为O(n)。

继续思考这个问题，在排序数组中，如果存在多个目标数字，那么这多个目标数字一定是连续排列的，那么我们只需要找到第一个目标数字的位置和最后一个目标数字的位置，就能计算出目标数字的总个数，而不需要一个一个的去查找统计。同样我们也是利用二分查找的方法来找到第一个目标数字和最后一个目标数字的位置。实现代码如下：

#include<stdio.h>

int GetFirstK(int *data, int length, int k,int start, int end)
{
	if(start>end)
		return -1;
	
	int midIndex = (start+end)/2;
	
	if(data[midIndex] == k)
	{
		if((midIndex > 0 && data[midIndex-1]!=k) || midIndex == 0)
			return midIndex;
		else
			end = midIndex - 1;
	}
	else if(data[midIndex] > k)
		end = midIndex - 1;
	else
		start = midIndex + 1;

	return GetFirstK(data,length,k,start,end);
}

int GetLastK(int *data, int length,int k,int start,int end)
{	
	if(start > end)
		return -1;
	
	int midIndex = (start+end)/2;
	
	if(data[midIndex] == k)
	{
		if((midIndex < length-1 && data[midIndex+1]!=k) || midIndex == length-1)
			return midIndex;
		else
			start = midIndex + 1;
	}
	else if(data[midIndex] > k)
		end = midIndex - 1;
	else
		start = midIndex + 1;

	return GetLastK(data,length,k,start,end);
}

int GetNumberOfK(int *data, int length, int k)
{
	int number = 0,first,last;
	
	if(data!=NULL && length>0)
	{
		first = GetFirstK(data,length,k,0,length-1);
		last = GetLastK(data,length,k,0,length-1);
		
		if(first > -1 && last > -1)
			number = last - first + 1;
	}	
	
	return number;
}

int main()
{
	int data[10] = {1,3,4,4,4,4,4,6,7,9};          /* 这里只是测试用例*/
	int number = GetNumberOfK(data,10,4);
	printf("%d\n",number);
	
	return 0;

}

运行结果如下：

上述代码中，GetFirstK和GerLastK都是用的二分查找法在数组中找到合乎要求的数字位置，它们的时间复杂度都是O(log n)，所以总的时间复杂度也是O(log n)，对比前面的O(n)有了一定的改进。