153 Find Minimum in Rotated Sorted Array – Medium¶

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.

You may assume no duplicate exists in the array.

Thoughts:¶

Using a O(n) iteration to find the min value in the array is too trivial and straight forward. So it is already clear enough that a Binary Search is needed here.

So this is a problem of modified Binary Search.

Solutions:¶

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length ==0) {
            return -1;
        }
        if (nums[0] <= nums[nums.length - 1]) {
            return nums[0];
        }
        return bs(nums, 0, nums.length - 1);
    }
    private int bs(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int mid = (start + end) / 2;
        if (mid > 0 && nums[mid -1] > nums[mid]) {
            return nums[mid];
        }
        if (nums[mid] >= nums[0]) {
            return bs(nums, mid + 1, end);
        }
        else {
            return bs(nums, start, mid - 1);
        }

    }
}

non-Recursion:

public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    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];
        }
    }
}