Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 153] Find Minimum in Rotated Sorted Array

Question

link

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.

Show Tags
Array Binary Search

Analysis

This question is very similar to [LeetCode 33] Search in Rotated Sorted Array. Note a few special cases.

Solution

Very good code can be found here and here.

My Code

public class Solution {
    public int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        return helper(num, 0, num.length - 1);
    }

    private int helper(int[] num, int left, int right) {
        if (num[left] <= num[right]) {
            return num[left];
        } else if (left + 1 == right) {
            return num[right];
        }
        int mid = left + (right - left) / 2;
        if (num[mid] > num[left]) {
            return helper(num, mid, right);
        } else {
            return helper(num, left, mid);
        }
    }
}