在一个非降序的数组中查找给定数值出现的频率，

要求空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)

比如：数组 {1,1,2,3,3,3,3,4,5}，查找3的频率，正确结果为4

很明显，非降序其实就是一个升序的，但允许重复的值出现而已，如果没有时间复杂度的O(logn)的要求，直接从头遍历就可以统计了，这是暴力的解法，显然这种算法的时间复杂度为

O(n),不符合要求，想来想去只能是二分法了，可以使用二分法进行递归，关于算法，在代码的注释中已经说明了

代码如下：

/** * 二分法查找重复出现的数字 * 非降序，有序数组，查找给定数值出现的频率 * @author ssj * */public class HalfFind {	static int count=0;		public static void main(String[] args) {		int[] arr = {1,1,2,3,3,3,3,4,5};//非降序，有序数组		half(arr, 0, arr.length-1, 3);//查找3在数组中出现的频率		System.out.println("频率="+count);	}			/**	 * 	 * @param arr	 * @param start 数组开始	 * @param end  数组结束	 * @param val 要查找的值	 */	public static  void half(int [] arr,int start,int end,int val) {		int mid = (start+end)/2;				if(arr[mid]==val) {			//发现了要找的值，统计加一			count++;						//因为中间值与要找的值相等，所以左右两半都可能还存在，需要两边继续查找			if(mid-1>=start) {				half(arr, start, mid-1, val);			}			if(mid+1<=end) {				half(arr, mid+1, end, val);			}					}else if(arr[mid]<val) {			//参考值大于中间值，只能在右边			if(mid+1<=end) {								half(arr, mid+1, end, val);			}		}else if(arr[mid]>val) {			//参考值小于中间值，只能在左边			if(mid-1>=start) {				half(arr, start, mid-1, val);							}		}			}}

运行结果：