题目：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例：

image.png

思路：

二分查找：查找要丢弃哪个部分
由题，可以看出，旋转点之前的数，一定大于等于数组第一位数；旋转点之后的数，一定小于数组第一位数；
例如：[4,5,6,7,0,1,2] ，旋转点是7之间，那么7之前的数，一定是大于等于4的；7之后的数一定是小于4的。
因此，假如中间点的数大于等于（必须等于）数组第一位数，那么，就要丢弃中间点左边部分的数，在中间点右边部分的数查找最小值；例如：{2,1}
否则，在包括中间点的左边部分查找最小值。
（有可能中间点就是最小值{6,7,1,3,4,5}）

代码：

//二分查找
class Solution {
    public int findMin(int[] nums) {
        //如果数组长度为1，或者数组没有发生旋转，即第一个数小于最后一个数，就直接返回
        if (nums.length < 2 || nums[0] < nums[nums.length - 1]) return nums[0];
        int l = 0;
        int h = nums.length - 1;
        while (l < h) {
            int mid = l + ((h - l) >>> 1);
            //如果中间点的数是大于数组第一位数
            //说明最小值在中间点右边
            //因为旋转点之前的数，一定大于等于数组第一位数
            //旋转点之后的数，一定小于数组第一位数
            if (nums[mid] >= nums [0]) {
                l = mid + 1;
            //否则，说明最小值在中间点左边
            //例如{6,7,1,3,4,5}
            } else {
                h = mid;
            }
        }
        return nums[l];
    }
}


//先排序（快排）
class Solution {
    public int findMin(int[] nums) {
        if (nums.length < 2) return nums[0];
        qSort(nums, 0, nums.length - 1);
        return nums[0];
    }

    public int Partition(int[] arr, int l, int h) {
        int pivot = arr[l];
        while (l < h) {
            while (l < h && arr[h] >= pivot) {
                h--;
            }
            arr[l] = arr[h];
            while (l < h && arr[l] <= pivot) {
                l++;
            }
            arr[h] = arr[l];
        }
        arr[l] = pivot;
        return l;
    }

    public void qSort(int[] arr, int l, int h) {
        if (l < h) {
            int pivotIndex = Partition(arr, l, h);
            qSort(arr, l, pivotIndex - 1);
            qSort(arr, pivotIndex + 1, h);
        }
    }

}

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