thesarfo

Reference

Minimum in a Rotated Sorted Array

Finding the minimum of a rotated sorted array by always keeping the leftmost element of whichever half is sorted.

views 0

Find the minimum element of a rotated sorted array of distinct values. (LeetCode 153)

Key idea: for any split point, one half is always fully sorted, and the leftmost element of a sorted half is its minimum. So each iteration, pick the leftmost element of whichever half is sorted as a candidate minimum, then discard that half.

public static int findMin(int []arr) {
    int low = 0, high = arr.length - 1;
    int ans = Integer.MAX_VALUE;
    while (low <= high) {
        int mid = (low + high) / 2;


        // search space is already sorted, arr[low] is the minimum in it
        if (arr[low] <= arr[high]) {
            ans = Math.min(ans, arr[low]);
            break;
        }


        if (arr[low] <= arr[mid]) { // left part is sorted
            ans = Math.min(ans, arr[low]);
            low = mid + 1; // eliminate left half
        } else { // right part is sorted
            ans = Math.min(ans, arr[mid]);
            high = mid - 1; // eliminate right half
        }
    }
    return ans;
}

An extra optimization: if arr[low] <= arr[high], the whole remaining search space is already sorted, so you can grab arr[low] directly and skip binary search entirely for that range — that check is already folded into the code above. Time: O(log n). Space: O(1).