Find Minimum in Rotated Sorted Array

LeetCode: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array nums of unique elements, return the minimum element.

Example:

  • Input: nums = [4,5,6,7,0,1,2]
  • Output: 0
1def findMin(nums: List[int]) -> int:
2    l, r = 0, len(nums) - 1
3    
4    while l < r:
5        mid = (l + r) // 2
6        
7        if nums[mid] > nums[r]:
8            l = mid + 1
9        else:
10            r = mid
11            
12    return nums[l]
Previous
Search Insert Position
Next
Search in Rotated Sorted Array
l
4
0
5
1
6
2
mid
7
3
0
4
1
5
r
2
6
Step 1 / 5
Step 1:
Initialize l=0, r=6. Compute mid=3.
Pointers: l=0, mid=3, r=6
Focus: compare @ [3, 6]