MediumBlind75ArrayBinary Search

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated. Find the minimum element.

Examples

Input
nums = [3,4,5,1,2]
Output
1

The original array was [1,2,3,4,5] rotated 3 times.

Input
nums = [4,5,6,7,0,1,2]
Output
0

The original array was [0,1,2,4,5,6,7] rotated 4 times.

Constraints

  • •n == nums.length
  • •1 <= n <= 5000
  • •-5000 <= nums[i] <= 5000
  • •All the integers of nums are unique.
  • •nums is sorted and rotated between 1 and n times.

Approaches

Scan through the array to find the minimum element.

CodeT: O(n) | S: O(1)
def find_min(nums):
    min_val = nums[0]
    for num in nums[1:]:
        if num < min_val:
            min_val = num
    return min_val

Compare mid element with right pointer to determine which half has the minimum.

CodeT: O(log n) | S: O(1)
def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

Same binary search but with early termination when array is not rotated.

Diagram

nums = [4,5,6,7,0,1,2] left=0,right=6,mid=3(7>2)->left=4 left=4,right=6,mid=5(1<2)->right=5 left=4,right=5,mid=4(0<1)->right=4 left=4,right=4->return nums[4]=0
CodeT: O(log n) | S: O(1)
def find_min(nums):
    if nums[0] <= nums[-1]:
        return nums[0]
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            return nums[mid + 1]
        if nums[mid] < nums[mid - 1]:
            return nums[mid]
        if nums[mid] > nums[0]:
            left = mid + 1
        else:
            right = mid - 1
    return nums[left]

Complexity Comparison

Linear Search
T: O(n)S: O(1)

Scan through the array to find the minimum element.

Binary Search
T: O(log n)S: O(1)

Compare mid element with right pointer to determine which half has the minimum.

Binary Search with Early Termination
T: O(log n)S: O(1)

Same binary search but with early termination when array is not rotated.

Common Mistakes

Using nums[mid] < nums[left] instead of nums[mid] > nums[right]

Not handling the case where the array is not rotated

Infinite loops when left and right are updated incorrectly

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems