Search In Rotated Sorted Array

Asked byAmazonFacebookMicrosoftLinkedInAppleBloomberg

Problem

Given a rotated sorted array of unique integers and a target value, return the index of target if it exists in the array, or -1 otherwise. The search must run in O(log n) time.

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

Constraints

1 <= nums.length <= 5000

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Binary Search pattern

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Look for this pattern when

The input is sorted, or partially sorted (like a rotated sorted array).
You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Read the full Binary Search guide →

Video walkthroughs

Original problem on LeetCode ↗