版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/u012515223/article/details/36869869

数字在排序数组中出现的次数 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 统计一个数字在排序数组中出现的次数.

通过折半查找, 找到首次出现的位置, 再找到末次出现的位置, 相减就可以.

时间复杂度O(logn).

代码:

/* * main.cpp * *  Created on: 2014.6.12 *      Author: Spike *//*eclipse cdt, gcc 4.8.1*/#include 
      
       #include 
       
        #include 
        
         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
         
           -1 && last > -1)		number = last-first+1;	return number;}int main(void){	int data[] = {1, 2, 3, 3, 3, 3, 4, 5};	int k = 3;	int result = GetNumberOfK(data, 8, k);	printf("result = %d\n", result);    return 0;}
         
        
       
      

输出:

result = 4