public class CountTimesInSortedArray {
/**
* 题目：在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
* 解法：使用二分查找的方法分别找出给定数字的开始和结束位置，最坏情况下时间复杂度为O(logn)
*/
public static void main(String[] args) {
int[] data={0,1,2,2,3,3,3,4,4,4,4,5};
for(int target:data){
int time=times(data,target);
System.out.println(target+","+time+" times");
}
}
public static int times(int[] array,int target){
if(array==null||array.length==0){
return -1;
}
return upTimes(array,target)-downTimes(array,target)+1;
}
public static int upTimes(int[] array,int target){
int low=0;
int high=array.length-1;
while(low<high){
int mid=(low&high)+(low^high)/2+1;//when low=high-1,let mid=high
int value=array[mid];
if(value<=target){
low=mid;
}else{
high=mid-1;
}
}
return low;
}
public static int downTimes(int[] array,int target){
int low=0;
int high=array.length-1;
while(low<high){
int mid=(low&high)+(low^high)/2;//when low=high-1,let mid=low
int value=array[mid];
if(value>=target){
high=mid;
}else{
low=mid+1;
}
}
return low;
}
}