Binary search isn’t just for finding an element in a sorted array. One of its most powerful applications is searching for a boundary or turning point. LeetCode 153: Find Minimum in Rotated Sorted Array is a perfect example of this pattern.
Problem
You are given a sorted array that has been rotated some number of times.
For example:
Original:
[1,2,3,4,5,6]
Rotated:
[3,4,5,6,1,2]Your task is to return the smallest element in the array.
The catch? Your solution must run in O(log n) time, ruling out a simple linear scan.
Understanding the Rotation
A rotated sorted array consists of two sorted halves.
Consider this example:
[4,5,6,7,0,1,2]Notice that:
- Left half:
[4,5,6,7] - Right half:
[0,1,2]
The minimum element is exactly where the rotation happens.
The challenge is figuring out which half contains that rotation point.
Key Observation
Instead of comparing with the left side, compare the middle element with the rightmost element.
Why?
The rightmost element tells us whether the middle lies in:
- the left sorted portion (before the rotation), or
- the right sorted portion (where the minimum exists).
Case 1:
nums[mid] > nums[r]
[4,5,6,7,0,1,2]
^
^
mid rHere:
nums[mid] > nums[r]Since 7 > 2, the minimum cannot be at mid or anywhere to its left.
It must be on the right side.
So we discard the left half:
l = mid + 1Case 2:
nums[mid] <= nums[r]
Example:
[4,5,6,0,1,2]
^
^
mid rNow:
nums[mid] <= nums[r]This means the middle is already inside the sorted portion containing the minimum.
The minimum could even be mid itself.
So we keep it:
r = midNotice we don’t do mid - 1 because we don’t want to accidentally discard the answer.
Why Does This Work?
Every iteration cuts the search space in half.
Eventually:
l == rAt this point, both pointers converge on the smallest element.
The answer is simply:
return nums[l]Python Solution
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid
return nums[l]Dry Run
Let’s trace the algorithm on:
nums = [3,4,5,6,1,2]Initial State
l = 0
r = 5
mid = 2
nums[mid] = 5
nums[r] = 2Since:
5 > 2Move right:
l = 3Second Iteration
l = 3
r = 5
mid = 4
nums[mid] = 1
nums[r] = 2Since:
1 <= 2Move left boundary:
r = 4Third Iteration
l = 3
r = 4
mid = 3
nums[mid] = 6
nums[r] = 1Since:
6 > 1Move right:
l = 4Now:
l == r == 4Return:
nums[4] = 1Complexity Analysis
Time Complexity
Each iteration halves the search space.
Time Complexity: O(log n)
Space Complexity
Only two pointers are used.
Space Complexity: O(1)
Takeaways
This problem highlights an important binary search pattern:
- You’re not searching for a specific value.
- You’re searching for the boundary where the sorted order breaks.
- Comparing
nums[mid]withnums[r]tells you which side still contains the minimum. - When
nums[mid] <= nums[r], keepmidbecause it might already be the answer.
Once you recognize this pattern, you’ll find it useful in many rotated-array problems, including searching for a target in a rotated sorted array and finding rotation points.
