Pseudo-code:

text
function findMin(nums):
    min_val = nums[0]
    for x in nums:
        if x < min_val:
            min_val = x
    return min_val

Time Complexity Analysis: The time complexity is O(N), where N is the length of the array, because we must inspect every element once.

Why it fails: While this approach produces the correct result, the problem explicitly mandates an O(log n) time complexity. A linear scan is too slow to satisfy the constraints of the optimal solution, particularly for large datasets where binary search is expected.

Core Insight for Find Minimum in Rotated Sorted Array

The key intuition for solving LeetCode 153 lies in understanding the structure of a rotated sorted array. A sorted array that has been rotated consists of two sorted subarrays:

1. Left Sorted Portion: Contains the larger values (e.g., [4, 5, 6, 7]).
2. Right Sorted Portion: Contains the smaller values (e.g., [0, 1, 2]).

The minimum element is the first element of the Right Sorted Portion. It is the only element in the array that is smaller than its predecessor (if a predecessor exists).

To find this element in O(log n) time, we cannot simply look for a specific target value. Instead, we use the sorted property to determine which half of the array contains the minimum.

The Comparison Logic: We compare the middle element (nums[mid]) with the rightmost element of the current search space (nums[right]).

1. If nums[mid] > nums[right]:

   • This implies that mid belongs to the Left Sorted Portion (the values that were rotated to the front).
   • The minimum value must be to the right of mid.
   • Visual: The values from left to mid are all greater than nums[right], so the drop-off (pivot) happens after mid.

2. If nums[mid] < nums[right]:

   • This implies that the range [mid, right] is sorted.
   • Therefore, mid is either the minimum itself or the minimum is to the left of mid.
   • The minimum cannot be to the right of mid because nums[mid] is already smaller than nums[right].

This logic allows us to discard half of the array reliably in every step, maintaining the invariant that the minimum element always exists within our current [left, right] bounds.

Execution Flow

Let's trace the algorithm with the input nums = [4, 5, 6, 7, 0, 1, 2].

1. Initial State:

   • left = 0, right = 6.
   • Array range: [4, 5, 6, 7, 0, 1, 2].

2. Iteration 1:

   • mid = 0 + (6 - 0) / 2 = 3.
   • nums[mid] is 7. nums[right] is 2.
   • Comparison: 7 > 2 is True.
   • Logic: The left part [4, 5, 6, 7] consists of large values. The minimum is to the right.
   • Update: left = mid + 1 = 4.

3. Iteration 2:

   • Current range: indices [4, 6]. Values: [0, 1, 2].
   • mid = 4 + (6 - 4) / 2 = 5.
   • nums[mid] is 1. nums[right] is 2.
   • Comparison: 1 > 2 is False.
   • Logic: nums[mid] < nums[right] means the range [mid, right] is sorted. The minimum is at mid or to its left.
   • Update: right = mid = 5.

4. Iteration 3:

   • Current range: indices [4, 5]. Values: [0, 1].
   • mid = 4 + (5 - 4) / 2 = 4.
   • nums[mid] is 0. nums[right] (index 5) is 1.
   • Comparison: 0 > 1 is False.
   • Logic: nums[mid] < nums[right].
   • Update: right = mid = 4.

5. Termination:

   • left (4) is no longer less than right (4).
   • Loop ends. Return nums[4], which is 0.

Proof of Correctness

The correctness relies on the invariant that the minimum element is always within the search range [left, right].

1. Base Case: Initially, the minimum is somewhere in the full array.
2. Inductive Step:
   • If nums[mid] > nums[right], the pivot (minimum) must be in the index range (mid, right]. By setting left = mid + 1, we preserve the minimum in the new range.
   • If nums[mid] < nums[right], the sequence from mid to right is ascending. The minimum cannot be in (mid, right]. Thus, it must be in [left, mid]. By setting right = mid, we preserve the minimum in the new range.
3. Termination: The range size decreases by at least 1 in each step (since mid < right is guaranteed by the floor division). Eventually, left == right, pointing to the single remaining candidate, which must be the minimum.

Reference Implementation

C++ Solution for LeetCode 153

cpp
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        // Loop until the search space converges to a single element
        while (left < right) {
            int mid = left + (right - left) / 2;

            // If mid element is greater than right element,
            // the minimum is in the right half (excluding mid)
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } 
            // If mid element is less than right element,
            // the minimum is in the left half (including mid)
            else {
                right = mid;
            }
        }

        // When left == right, we have found the minimum
        return nums[left];
    }
};

Java Solution for LeetCode 153

java
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        // Loop until pointers meet
        while (left < right) {
            int mid = left + (right - left) / 2;

            // Compare mid with the right boundary
            if (nums[mid] > nums[right]) {
                // Minimum is to the right
                left = mid + 1;
            } else {
                // Minimum is at mid or to the left
                right = mid;
            }
        }

        return nums[left];
    }
}

Python Solution for LeetCode 153

python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            # If the middle element is greater than the rightmost element,
            # the minimum value must be in the right portion.
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                # Otherwise, the minimum is at mid or in the left portion.
                right = mid
                
        return nums[left]

Q: Why do I return the wrong value when the array is not rotated?

• Mistake: Assuming the array is always rotated and not handling the case where nums is [1, 2, 3].
• Why: Some logic explicitly looks for a drop (e.g., nums[i] > nums[i+1]). If the array is fully sorted, this drop never exists.
• Consequence: The algorithm might return the last element or crash. The binary search logic provided above naturally handles the non-rotated case (it will keep moving right to mid until it hits index 0).