0030 - Find Minimum in Rotated Sorted Array - Revise

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

[3,4,5,6,1,2] if it was rotated 4 times. [1,2,3,4,5,6] if it was rotated 6 times. Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Example 1:

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

Output: 1 Example 2:

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

Output: 0 Example 3:

Input: nums = [4,5,6,7]

Output: 4

https://www.youtube.com/watch?v=5AM_xIetqvQ

1. Core concept used - Binary Search
2. Find mid using left and right
3. If mid>right, then the lowest value is on right side. Update left = mid+1
4. if mid<right, then the lowest value in on left side. Update right = mid
5. When left=right=mid then we get our answer, at this point loop will exit

In [24]:

def findMin(nums):
    left,right=0,len(nums)-1
    while left<right:
        mid=left+((right-left)//2)
        if nums[mid]>nums[right]:
            left=mid+1
        else:
            right=mid
    return nums[left]

In [25]:

findMin([3,4,5,6,1,2])

Out[25]:

1

In [26]:

findMin([2,3,4,5,1])

Out[26]:

1

In [27]:

2+3//2

Out[27]:

3