Search in Rotated Sorted Array
MediumOne half is always sorted — check which
Problem
A sorted array of distinct integers has been rotated at an unknown pivot. Return the index of target, or -1 if it is not present.
One half is always sorted — check if the target lies in it, then binary-search the right side.
The idea
Compare the middle with the left end to find which half is properly sorted, then test whether the target lies inside that sorted half's range. If it does, search there; otherwise search the other half.
The trick
- Identify the sorted half first, then decide with a simple range test.
- With duplicates the comparison can be ambiguous — shrink both ends by one and retry.
- O(log n) for distinct values.
Step 1 of 6. Brute force: walk left to right until you find 0. Values: 4, 5, 6, 7, 0, 1, 2. target 0.
Scan one by one.
1// ignore the rotation, just scan2for (let i = 0; i < n; i++)3 if (nums[i] === target) return i;4return -1;Input
- array
- [4, 5, 6, 7, 0, 1, 2]
Memory
- i
- —
- target
- 0
- checked
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- Output:
- 4
- Explanation:
- 0 is found at index 4.
Example 2
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2], target = 3
- Output:
- -1
- Explanation:
- 3 is absent → -1.
Example 3
- Input:
- nums = [1], target = 1
- Output:
- 0
- Explanation:
- Found at index 0.
Constraints
- 1 <= n <= 10^4
- -10^4 <= nums[i], target <= 10^4
- All values are distinct.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.