Problem

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

 Notice

You may assume no duplicate exists in the array.

Example
Given [4, 5, 6, 7, 0, 1, 2] return 0

思路(复杂一点)

1. 因为O(n)的时间就可以得到答案, 并没有利用到rotated sorted的特征, 所以应该用二分法
2. 如果[start] < [end] 直接return [start], 因为是sorted的
3. 否则[start] > [end]
   1. [mid] < [start], end = mid
   2. [end] < [mid], start = mid

    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;

        while (start + 1 < end) {
            if (nums[start] < nums[end]) {
                return nums[start];
            }
            int mid = start + (end - start) / 2;
            if (nums[mid] > nums[start]) {
                start = mid;
            } else if (nums[mid] < nums[end]){
                end = mid;
            } else {

            }
        }
        if (nums[start] < nums[end]) {
            return nums[start];
        }
        return nums[end];
    }

思路(concise点的)

• target = nums[end]
• find the first element <= target

    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        int target = nums[nums.length - 1];

        // find the first element <= target
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] <= target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums[start] <= target) {
            return nums[start];
        } else {
            return nums[end];
        }
    }