版权声明：本文为博主原创文章，未经博主同意不得转载。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 <stdio.h>
#include <stdlib.h>
#include <string.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<length-1 && data[middleIndex+1]!=k) || middleIndex == length-1)
return middleIndex;
else
start = middleIndex+1;
} else if (middleData < k)
start = middleIndex+1;
else
end = middleIndex-1;
return GetLastK(data, length, k, start, end);
}
int GetNumberOfK (int* data, int length, int k) {
int number = 0;
if (data == NULL && length <= 0)
return number;
int first = GetFirstK(data, length, k, 0, length-1);
int last = GetLastK(data, length, k, 0, length-1);
if (first > -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