如何求数字在排序数组中出现的次数

如何求数字在排序数组中出现的次数2015-10-12题目: 统计一个数字在排序数组中出现的次数.

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

时间复杂度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;elseend = middleIndex-1;} else if （middleData>k）end = middleIndex-1;elsestart = 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;elsestart = middleIndex+1;} else if （middleData < k）start = middleIndex+1;elseend = 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
", result）;return 0;}

输出:

result = 4

作者：csdn博客 Caroline-Wendy