Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

What is this problem about?

The Find Minimum in Rotated Sorted Array interview question is a classic search optimization task. You are given an array that was originally sorted in ascending order but then rotated at an unknown pivot (e.g., [4, 5, 6, 7, 0, 1, 2]). Your goal is to find the minimum element in $O(\log N)$ time. This Find Minimum in Rotated Sorted Array coding problem tests your ability to adapt standard search algorithms to "broken" sorted properties.

Why is this asked in interviews?

This is a standard question at almost every major tech company, including Apple, Microsoft, and Amazon. It evaluates your understanding of Binary Search interview patterns. Specifically, it checks if you can identify which half of an array is still sorted and use that information to discard half of the search space, even when the global sorted property is violated.

Algorithmic pattern used

The problem is solved using a modified Binary Search.

1. Initialize: left = 0, right = n - 1.
2. Loop: Compare nums[mid] with nums[right].
3. Discard Half:
   • If nums[mid] > nums[right], the minimum must be in the right half (because the "drop" occurred there). Move left = mid + 1.
   • If nums[mid] < nums[right], the right half is sorted normally, so the minimum is either at mid or to its left. Move right = mid.
4. Result: When left == right, you've found the pivot point, which is the minimum.

Example explanation

Array: [4, 5, 6, 7, 0, 1, 2]

• left=0 (4), right=6 (2), mid=3 (7).
• $7 > 2$, so move left to index 4. Array is now [0, 1, 2].
• left=4 (0), right=6 (2), mid=5 (1).
• $1 < 2$, so move right to index 5. Array is now [0, 1].
• left=4 (0), right=5 (1), mid=4 (0).
• $0 < 1$, so move right to index 4.
• left == right. Result: 0.

Common mistakes candidates make

• Linear Search: Using a single loop ($O(N)$), which misses the logarithmic requirement.
• Handling No Rotation: Forgetting that if the array isn't rotated at all, nums[0] is the minimum.
• Termination condition: Using left <= right which can lead to infinite loops if not careful with the mid update.

Interview preparation tip

Always look for the sorted property. If an array is "mostly" sorted, Binary Search is usually the answer. Practice variations of this, such as searching for a target in a rotated array, to strengthen your pointer logic.