Find Minimum in Rotated Sorted Array

1. Problem Description

An array of length n was originally sorted in ascending order and then rotated between 1 and n times. For example, the original array nums = [0,1,2,4,5,6,7] may become: After 4 rotations: [4,5,6,7,0,1,2] After 7 rotations: [0,1,2,4,5,6,7] Note that rotating [a[0], a[1], a[2], ..., a[n-1]] once produces [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given an array nums with distinct values that was originally sorted in ascending order and then rotated as described above, find and return its minimum element.

You must design an algorithm with O(log n) time complexity.

2. Approach

3. Implementation

func findMin(nums []int) int {
    left := 0
    right := len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        }else {
            right = mid
        }
    }
    return nums[left]
}

4. References

• Binary Search: Why Are the Two Sides Asymmetric? Why Compare mid with right? (C++, Java, Python3) - Find Minimum in Rotated Sorted Array - LeetCode