Search in Rotated Sorted Array

Difficulty: Medium · Topic: Searching

An ascending array of distinct integers was rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given nums and target, return its index, or -1. Aim for O(log n) — at each step one half is still sorted, and you can tell which.

Examples

search_rotated([4,5,6,7,0,1,2], 0)
→ 4

search_rotated([4,5,6,7,0,1,2], 3)
→ -1

search_rotated([5,1,3], 5)
→ 0

Target complexity: time O(log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.