Search in Rotated Sorted Array I
MediumOne half is always sorted — use it
A rotated sorted list still has one sorted half at each step — spot the sorted half and jump into the right one.
The idea
Even after rotation, at least one side of mid is fully sorted. Check which side is sorted and whether the target lies within it to decide where to search.
lo
hi
5
6
7
0
1
2
4
0
1
2
3
4
5
6
Step 1 of 4. Even rotated, one side of mid is always sorted. Target = 1. Values: 5, 6, 7, 0, 1, 2, 4. Pointers: lo at index 0, hi at index 6.
1/4
Optimal
timeO(log n)spaceO(1)
Pick the sorted half each step.
1while (lo <= hi) {2 const mid = (lo + hi) >> 1;3 if (nums[mid] === target) return mid;4 if (nums[lo] <= nums[mid]) { // left sorted5 if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;6 else lo = mid + 1;7 } else { // right sorted8 if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;9 else hi = mid - 1;10 }11}Input
- array
- [5, 6, 7, 0, 1, 2, 4]
Memory
- lo
- = 0 [5]
- hi
- = 6 [4]
- mid
- —
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.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.