LeetCode: 153. Find Minimum in Rotated Sorted Array

LeetCode: 153. Find Minimum in Rotated Sorted Array

Summary

Given a rotated sorted array nums with unique elements, return the minimum element.

You must write an algorithm that runs in O(log n) time.

Approach

Binary search.

If the array is not rotated, the minimum is the first element.
With rotation, the minimum is inside the unsorted side of the current search range.

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

• mid = 7, right = 2
• Since nums[mid] > nums[right], the minimum must be in the right half.

Another example: [3,4,5,1,2]

• mid = 5, right = 2
• Again, nums[mid] > nums[right], so move to the right half.

Function

Initialization:

• left = 0, right = len(nums) - 1

While left < right:

• mid = (left + right) // 2
• If nums[mid] > nums[right]:
  • left = mid + 1 (minimum is in the right half)
• Else:
  • right = mid (minimum is at mid or in the left half)

Return nums[left].

Complexity

Time complexity: O(logN) using binary search.
Space complexity: O(1).