Blind 75 · Binary Search

Search in Rotated Sorted Array

Medium

Problem

An ascending array of unique integers was rotated at some unknown point. Given the array and a target, return the index of the target, or -1 if it is absent.
Your algorithm must run in O(log n).

Examples

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1], target = 0
Output: -1

Example 4:
Input: nums = [5,1,3], target = 3
Output: 2

Constraints

1 <= nums.length <= 5000
-10^4 <= nums[i], target <= 10^4
All values are unique.

Prerequisites

Binary search — halving a range, and being precise about which half is guaranteed to hold the answer.

How to think about it

1. Search the Half That Is Sorted Optimal

Intuition

The rotation point lies in one half, which means the other half is cleanly sorted — and in a sorted half, a simple range check says whether the target is inside. So each step: work out which half is sorted, ask whether the target lives there, and recurse into that half or the other. Ordinary binary search with one extra question.

Algorithm

1. Take the middle; if it is the target, done.
2. If the left half is sorted (left value at most middle value), check whether the target lies within it and move accordingly.
3. Otherwise the right half is sorted; do the same test there.
4. Exhausting the range means the target is absent.

Time & Space

Time O(log n). Space O(1).