Find Minimum in Rotated Sorted Array | Leetcode

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.

---

Solution: Use a modified binary search. In each sub-array, if the first number is less than the last number, then this sub-array is sorted, so just return the first number. If this sub-array is not sorted, then break the sub-array into two halves and return the minimum of the minimum numbers from each half.

public class Solution {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    } 
    
    private int findMin(int[] nums, int lo, int hi) {
        if (lo >= hi) return nums[hi];

        // If sub-array is sorted, return the first number.
        boolean isSorted = (nums[lo] < nums[hi]);
        if (isSorted) return nums[lo];

        // If sub-array is not sorted, then need to search in both halves.
        int mid = lo + (hi - lo) / 2;
        return Math.min(findMin(nums, lo, mid), findMin(nums, mid + 1, hi));
    }
}