Find Minimum in Rotated Sorted Array

Medium

The problem

A list of different numbers was sorted from smallest to biggest, then rotated: some numbers from the front were moved to the back, like [1, 2, 3, 4, 5] becoming [3, 4, 5, 1, 2]. Given the rotated list, return its smallest number.

Example 1
Input: nums = [3, 4, 5, 1, 2]
Output: 1
The list is the sorted list 1..5 with 1, 2 moved to the back.
Example 2
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
The smallest number is 0.
Example 3
Input: nums = [11, 13, 15, 17]
Output: 11
Rotating by 0 leaves the list as it was.

Limits

1 ≤ nums.length ≤ 100,000
All numbers are different
The list was sorted and then rotated 0 or more times

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Compare the middle with the right end: that tells you which side contains the "break".

The idea

If nums[mid] > nums[hi] the minimum is right of mid (lo=mid+1); otherwise it is at mid or left (hi=mid).

Target: O(log n) time

Go function shape

func findMin(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// SearchRotated: target in a rotated sorted slice of distinct values, or -1.
// Step 1: find the rotation point (index of the minimum). Step 2: binary search the right half.
func SearchRotated(nums []int, target int) int {
	n := len(nums)
	if n == 0 {
		return -1
	}
	// the minimum is the first element that is <= the last element
	pivot := firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })
	// treat the slice as sorted with a shifted index: real = (i + pivot) % n
	i := firstTrue(n, func(i int) bool { return nums[(i+pivot)%n] >= target })
	if i < n && nums[(i+pivot)%n] == target {
		return (i + pivot) % n
	}
	return -1
}

// FindMin: minimum of a rotated sorted slice of distinct values.
func FindMin(nums []int) int {
	n := len(nums)
	return nums[firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })]
}

Read the lesson: Binary Search