153. Find Minimum in Rotated Sorted Array

Intuition

In a rotated sorted array, the minimum element is the only element that is smaller than its previous element, and it marks the point of rotation. If the array is not rotated at all, the first element is the minimum.

Using binary search, we can efficiently find the rotation point by identifying where the order breaks in the array.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

public int findMin(int[] nums) {
    // If the array is already sorted, the first element is the minimum
    if (nums[0] <= nums[nums.length - 1]) return nums[0];

    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        // Check if mid is the pivot point (greater than next element)
        boolean isPivotPoint = (mid + 1 < nums.length && nums[mid] > nums[mid + 1]);

        if (isPivotPoint) {
            return nums[mid + 1]; // Found the minimum
        }

        // If mid element is less than the last element, the min is on the left
        if (nums[mid] < nums[nums.length - 1]) {
            right = mid - 1;
        } else {
            // Else, the min is on the right
            left = mid + 1;
        }
    }

    return -1; // This should not be reached if input is valid
}