Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array numsof unique elements, return the minimum element of this array.

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

Example 1:

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

Example 2:

  • Input: nums = [11,13,15,17]
  • Output: 11

My Idea

Since the required Time Complexity is O(log n) we need to use binary search. If the array we need to examine hasn’t been rotated, we just need the leftmost value. If it has been rotated, however, we essentially have two parts of the array a left and a right one, both of which are sorted.The idea here is that for each mid we calculate, we check if it’s bigger than the value at the right pointer, which would mean that it’s in the left sorted part, so we need to continue our search to the right of it. If it is lower that means we’re in the right sorted part and need to continue to the left of it.

My solution

# Time Complexity: O(log n)
def findMin(nums: list[int])->int:
    l=0
    r=len(nums)-1
    minVal=nums[l]

    while(l<=r):
        if nums[l]<nums[r]:
            minVal=min(minVal,nums[l])
            break
        mid=(l+r)//2
        minVal=min(minVal,nums[mid])
        if nums[mid]>=nums[r]:
            l=mid+1
        else:
            r=mid-1
    return minVal