Search 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. Given the rotated list and a target, return the index of the target, or -1 if it is not in the list.

Example 1
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
nums[4] is 0.
Example 2
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
3 is not in the list.
Example 3
Input: nums = [1], target = 0
Output: -1
The only number is 1.

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

At any mid, at least one half is perfectly sorted. Can you tell which, and whether the target lives in it?

The idea

Decide which half is sorted (nums[lo] ≤ nums[mid]); if the target lies inside that sorted range go there, else go to the other half.

Target: O(log n) time

Go function shape

func search(nums []int, target 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