Problem Statement (LeetCode 153)

Suppose an array of length n sorted in strictly ascending order is rotated between 1 and n times. For example, the sorted 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 (returning to its original order).

Rotating an array [a[0], a[1], a[2], ..., a[n - 1]] once produces [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 in $\mathcal{O}(\log n)$ time.

Examples

Example 1:
Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.

Example 2:
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 5, 6, 7] rotated 4 times.

Example 3:
Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: The original array was rotated 4 times (full cycle).

Algorithmic Insight: Locating the Inflection Point via Binary Search

A rotated sorted array of unique elements consists of at most two monotonically increasing segments separated by an inflection point (the minimum element). Every element in the left rotated segment is strictly greater than every element in the right segment.

Why Comparing nums[mid] Against nums[high] Is Optimal

During binary search over the interval [low, high] with midpoint mid = low + ((high - low) >> 1), comparing nums[mid] against the right boundary nums[high] unambiguously identifies which half contains the minimum:

1. Case 1 (nums[mid] > nums[high]): Because the array would be non-decreasing if unrotated, seeing a midpoint strictly greater than the right boundary proves the drop-off (inflection point) lies strictly to the right of mid. Therefore, mid itself cannot be the minimum, and we safely advance low = mid + 1.
2. Case 2 (nums[mid] < nums[high]): The subarray nums[mid..high] is monotonically increasing. Thus, no element to the right of mid can be smaller than nums[mid], meaning the minimum lies in [low..mid]. We keep mid as a candidate by setting high = mid.

Notice that comparing nums[mid] with nums[low] instead would be ambiguous when nums[low] < nums[mid], because both a fully unrotated array ([1, 2, 3, 4, 5], minimum on the left) and a rotated array ([4, 5, 6, 1, 2], minimum on the right) satisfy nums[low] < nums[mid].

Dry-Run Trace on nums = [4, 5, 6, 7, 0, 1, 2]

C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

int findMinimum(const vector<int>& arr) {
    int low = 0;
    int high = static_cast<int>(arr.size()) - 1;

    while (low < high) {
        int mid = low + (high - low) / 2;

        // Inflection point lies strictly to the right of mid
        if (arr[mid] > arr[high]) {
            low = mid + 1;
        } else {
            // Minimum is either at mid or to the left of mid
            high = mid;
        }
    }

    return arr[low];
}

int main() {
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
    cout << "The minimum element is: " << findMinimum(arr) << endl;
    return 0;
}

TypeScript Implementation

export function findMin(nums: number[]): number {
  let low = 0;
  let high = nums.length - 1;

  while (low < high) {
    const mid = low + ((high - low) >> 1);

    if (nums[mid] > nums[high]) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }

  return nums[low];
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(\log n)$. Each iteration halves the active search interval [low, high] and performs a single constant-time comparison, requiring at most $\lceil \log_2(n) \rceil$ steps.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space, as the search operates entirely in-place using three integer index pointers (low, high, and mid).