数字在排序数组中出现的次数

/*************************************************************************
题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}
和数字3，由于3在这个数组中出现了4次，因此输出4。
**************************************************************************/
/*
解题思路：
先获取第一个为k的索引，再获取第二个为k的索引，然后再用两者之差作为返回次数。
用二分法查找索引，索引时间复杂度为O(logN)；
*/
#include<stdio.h>

int getFirstK(int* data, int length, int k, int start, int end)
{
	if(start > end)
		return -1;

	int middleIndex = (start+end)/2;
	int middleData = data[middleIndex];

	if(middleData == k)
	{
		if((middleIndex>0 && data[middleIndex-1] != k)
			|| middleIndex == 0)
			return middleIndex;
		else
			end = middleIndex-1;
	}
	else if(middleData > k)
		end = middleIndex - 1;
	else
		start = middleIndex + 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 middleIndex = (start+end)/2;
	int middleData = data[middleIndex];

	if(middleData == k)
	{
		if((middleIndex>0 && data[middleIndex+1] != k)
			|| middleIndex == length-1)
			return middleIndex;
		else
			start = middleIndex + 1;
	}
	else if(middleData > k)
		end = middleData - 1;
	else
		start = middleData + 1;

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

int getNumberOfK(int* data, int length, int k)
{
	if(data == NULL || length<=0)
		return 0;

	int firstIndex = getFirstK(data,length,k,0,length-1);
	int lastIndex = getLastK(data,length,k,0,length-1);
	int number = 0;
	if(firstIndex > -1 && lastIndex > -1)
		number = lastIndex-firstIndex+1;
	
	return number;
}
void test()
{
	const int length = 8;
	int arr[length] = {1,2,3,3,3,3,4,5};
	printf("%d\n",getNumberOfK(arr,length,3));
}
int main()
{
	test();
	return 0;
}

数字在排序数组中出现的次数,布布扣,bubuko.com

数字在排序数组中出现的次数

原文：http://blog.csdn.net/walkerkalr/article/details/21443149