题目:
在排序数组中,找出给定数字出现的次数
思路:
既然出现排序数组,很容易想到二分查找,时间复杂度为O(logn);
先通过二分查找找到最左边出现该数字的下标left(如果没找到,则返回-1),然后通过二分查找找到最右边出现该数字的下表right(如果没找到,则返回-1),然后right-left+1就是出现的次数;
代码:
#include <iostream> using namespace std; int BinarySearchCount(int *array,int len,int data){ if(len<1) return -1; int left=0; int right=len-1; int mid; int leftIndex=-1; // find the left index while(left<=right){ mid=left+((right-left)>>1); if(array[mid]==data){ leftIndex=mid; right=mid-1; } else if(array[mid]<data) left=mid+1; else right=mid-1; } // find the right index left=0; right=len-1; int rightIndex=-1; while(left<=right){ mid=left+((right-left)>>1); if(array[mid]==data){ rightIndex=mid; left=mid+1; } else if(array[mid]<data) left=mid+1; else right=mid-1; } if(leftIndex!=-1 && rightIndex!=-1) return rightIndex-leftIndex+1; else return 0; } int main() { int arr[]={0,1,2,3,3,3,3,3,3,3,4,5,6,7,13,19}; int len=sizeof(arr)/sizeof(arr[0]); cout << BinarySearchCount(arr,len,18) << endl; return 0; }