Find Minimum In Rotated Sorted Array - rFronteddu/general_wiki GitHub Wiki

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

class Solution {
    public int findMin(int[] nums) {
        // use binary search and don't stop until left == right, at which point we found the minimum
        // in this rotated sorted array
        
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                // The minimum element is on the right side
                left = mid + 1;
            } else {
                // The minimum element is on the left side (or mid itself)
                right = mid;
            }
        }

        // At this point, left == right, and it is the minimum element
        return nums[left];
    }
}