在排序数组中，找出给定数字的出现次数

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;
	}
}