《剑指offer》:[38]数字在排序数组中出现的次数

#include <iostream>
using namespace std;
int arr[8]={1,2,3,3,3,3,4,5};
int GetFirstK(int *array,int k,int length,int start ,int end)
{
	if(start>end)
		return -1;
	int middleIndex=(start+end)/2;
	int middledata=array[middleIndex];
	if(middledata==k)
	{
		if(middleIndex>0 && array[middleIndex-1]!=k || middleIndex==0)
			return middleIndex;
		else
			end=middleIndex-1;
	}
	else if(middledata>k)
		end=middleIndex-1;
	else
		start=middleIndex+1;
	return GetFirstK(array,k,length,start,end);
}


int GetLastK(int *array,int k,int length,int start,int end)
{
	if(start>end)
		return -1;
	int middleIndex=(start+end)/2;
	int middledata=array[middleIndex];
	if(middledata==k)
	{
		if(middleIndex<length-1 && array[middleIndex+1]!=k || middleIndex==length-1)
			return middleIndex;
		else
			start=middleIndex+1;
	}
	else if(middledata>k)
		end=middleIndex-1;
	else
		start=middleIndex+1;
	return GetLastK(array,k,length,start,end);
}
int GetNumK(int *array,int length,int k)
{
	int number=0;
	if(array!=NULL && length>0)
	{
		int first=GetFirstK(array,k,length,0,length-1);
		int last=GetLastK(array,k,length,0,length-1);
		if(first>-1 && last>-1)
			number=last-first+1;
		else
			return 0;
	}
	return number;
}
int main()
{
	int num=GetNumK(arr,8,3);
	cout<<"3出现的次数是："<<num<<endl;
	system("pause");
	return 0;
}

运行结果是：

《剑指offer》:[38]数字在排序数组中出现的次数

原文：http://blog.csdn.net/gogokongyin/article/details/51712624