/** * 题目:在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。 * 解法:使用二分查找的方法分别找出给定数字的开始和结束位置,最坏情况下时间复杂度为O(logn) */ #include<stdio.h> #include<stdlib.h> //全局变量 int arr[] = {0,1,1,2,2,2,2,4,4,4}; //测试数组 int size = sizeof(arr) / sizeof(*arr); //数组元素个数 int getUpper(int arr[], int key){//获取某个元素最后出现位置 int low = 0, high = size - 1; //其实是一个递归迭代 while(low < high){ int mid = (low + high + 1) / 2; if(arr[mid] <= key) //当要查找的值比中位数大于等于时,把查找的低位限制为mid low = mid; else //当要找的值比 中位数小时,,把查找的高位限制为mid-1 high = mid - 1; } // 返回最后出现位置 return low; } int getLower(int arr[], int key){//获取某个元素第一次出现位置 int low = 0, high = size - 1; while(low < high){ int mid = (low + high) / 2; //当要找的值比 中位数小于等于时,,把查找的高位限制为mid+1 if(arr[mid] >= key) high = mid; else //当要找的值比 中位数大时,,把查找的低位限制为mid+1 low = mid + 1; } //返回第一次出现位置 return low; } int main(){ for(int i = 0; i < size; i ++) printf("%d 出现 %d 次\n",arr[i],getUpper(arr,arr[i]) - getLower(arr,arr[i]) + 1); getchar(); }