Chapter 9 - Binary Search Problems

Question 1

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.
(Solve in O(log n) time and O(1) space complexity)
Example 1:

Input: [3,4,5,1,2]
Output: 1

Answer 1

Find the mid element of the array.

4,5,6,7 -> inflection point -> 0,1,2

If mid element > the first element of the array -> look for the inflection point on the right of mid

If mid element < first element of the array -> look for the inflection point on the left of mid

We stop our search when we find the inflection point when either of the two conditions is satisfied:

nums[mid] > nums[mid + 1] Hence, mid+1 is the smallest.

nums[mid - 1] > nums[mid] Hence, mid is the smallest.

    def findMin(self, nums):
        if len(nums) == 1:
            return nums[0]

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

    if nums[right] > nums[0]:
        return nums[0]

    while right >= left:
        mid = left + (right - left) / 2

       if nums[mid] > nums[mid + 1]:
            return nums[mid + 1]
        if nums[mid - 1] > nums[mid]:
            return nums[mid]

        if nums[mid] > nums[0]:
            left = mid + 1
        else:
            right = mid - 1