Search in Rotated Sorted Array
Search in Rotated Sorted Array
A sorted array of distinct integers has been rotated at some unknown pivot. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given such a rotated sorted array and a target value, find the index of the target. Your solution must run in O(log n) time. Your solve(...) function receives these inputs directly as ready-made arguments — no input reading or parsing needed. Just compute and return the answer.
Input format — only if your code reads from stdin
Input format (stdin): - First line: two integers n (array size) and target - Second line: n space-separated integers (the rotated sorted array) Output: the 0-based index of the target, or -1 if not present.
Approach
Modified binary search: at each step, one of the two halves is guaranteed to be sorted. If arr[low] ≤ arr[mid], the left half is sorted — check if target falls in [arr[low], arr[mid]) and narrow accordingly. Otherwise the right half is sorted.
Input
Output
- •
1 ≤ n ≤ 5000, -10^4 ≤ elements, target ≤ 10^4, all elements are distinct
More Binary Search problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards