旋转数组找最小值

旋转数组

[1,2,3,4,5,6,7,8] 经旋转得到 [4,5,6,7,8,1,2,3] ,他就是旋转数组

要求: 找到最小值，时间复杂度尽可能低

分析

如上，可以看到，旋转数组的第一个值可以将整个数组划分为两个部分，小于它的和大于等于它的，那么我们可以二分，找到的是大于等于首部的，就往右去搜索。找到小于首部的，就往左去搜索。

代码

public class Main {
    private static int first;
    public static void main(String[] args) {
        int[] arr = new int[]{4,5,6,7,8,9,10,11,1,2,3};
        first = arr[0];
        int min = findMin(arr,0,arr.length-1);
        System.out.println(min);
    }

    /**
     * 在递归的任何阶段保持 start左边的一定大于等于首部，end右边的一定小于首部
     * @param arr
     * @param start 开始位置
     * @param end 结束位置
     * @return
     */
    private static int findMin(int[] arr,int start,int end) {
        // System.out.println(start+":"+end);
        if(start > end){
            return arr[start];
        }
        int mid = start + ((end - start)>>1);
        if(arr[mid] >= first){
            return findMin(arr,mid+1,end);
        }else{
            return findMin(arr,start,mid-1);
        }
    }
}