You are given an integer array nums that was originally sorted in ascending order with distinct values. Before it reached you, it may have been left-rotated at an unknown pivot index k (1 <= k < nums.length), moving the first k elements to the back. For example, [0,1,2,4,5,6,7] rotated at pivot 3 becomes [4,5,6,7,0,1,2].
Given the possibly rotated array nums and an integer target, return the index of target in nums, or -1 if it is not present.
Your algorithm must run in O(log n) time.
nums[lo] <= nums[mid], there is no break between lo and mid, so the left half is sorted; otherwise the break is on the left, which forces the right half [mid..hi] to be sorted.nums[lo] <= target < nums[mid] and nums[mid] < target <= nums[hi]. The value nums[mid] was already compared against target, so it is excluded — but nums[lo] and nums[hi] have not been examined yet and must stay inclusive.nums[lo] == nums[mid] == nums[hi] you cannot tell which half is sorted — shrink both ends by one and continue. Correctness survives, but the worst case degrades to O(n). That is the problem Search in Rotated Sorted Array II.nums[mid] against nums[hi]: if nums[mid] > nums[hi] the minimum lies right of mid, otherwise it is at mid or to its left. That is Find Minimum in Rotated Sorted Array.Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 The sorted array [0,1,2,4,5,6,7] was rotated at pivot 4; the value 0 now sits at index 4.
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 3 does not appear anywhere in the array.
Input: nums = [1], target = 0 Output: -1 A single-element array that does not contain the target.
- 1 <= nums.length <= 5000 - -10^4 <= nums[i] <= 10^4 - All values of nums are unique - nums is an ascending array that is possibly rotated - -10^4 <= target <= 10^4
A rotated sorted array looks broken, but it hides exactly enough order for binary search to survive. This tutorial builds the single extra question — which half is sorted? — that upgrades the classic lo/hi loop from plain sorted arrays to rotated ones.
[lo..hi] always contains the target if it exists at all.You receive an ascending array of distinct integers that may have been left-rotated at an unknown pivot, plus a target. Return the index of target, or -1 if it is absent — in O(log n) time.
Worked example 1 — nums = [4,5,6,7,0,1,2], target = 0
index: 0 1 2 3 4 5 6
value: 4 5 6 7 0 1 2
[ run A: 4..7 ][ run B: 0..2 ]
target 0 lives in run B → answer: 4
Worked example 2 — nums = [1], target = 0
value: 1 (rotation by zero — a fully sorted array is valid input) 0 is not present → answer: -1
Asking two or three sharp questions before coding tells the interviewer you have already seen where this problem bites.
“Are all values guaranteed to be distinct?”
Yes — and it matters. With duplicates the sorted-half test can become ambiguous; that is the harder follow-up variant.
“Can the rotation be zero, leaving the array fully sorted?”
Yes. Your solution must not assume a pivot exists — a fully sorted array is valid input.
“Can the array have a single element?”
Yes — n >= 1. The loop must handle lo == hi == mid cleanly.
“What do I return when the target is absent?”
Return -1 — never an exception or a sentinel index.
“How large can the array get?”
Up to 5000 elements — a linear scan would actually pass, so the O(log n) requirement is the real test. The interviewer wants the binary-search insight, not merely a fast-enough answer.
Before I code, a few quick checks.
All values are distinct, correct? With duplicates the half-detection trick weakens, so I want to confirm.
The array may be rotated by zero — so a fully sorted array is valid input, and a single element is possible too.
Since O(log n) is required, I will adapt binary search rather than scan.
Rotating a sorted array moves a suffix to the front. Whatever the pivot, you end up with two ascending runs back to back — and because values are distinct, every element of the first run is larger than every element of the second.
sorted: 0 1 2 4 5 6 7
rotated: 4 5 6 7 | 0 1 2
run A run B (all of A > all of B)Cut the window [lo..hi] at mid. The rotation break point lies in only one of the two halves — the other half contains no break, so it is fully sorted. One comparison detects it: if nums[lo] <= nums[mid], there is no break between lo and mid, so the left half is sorted; otherwise the break is on the left, which forces the right half [mid..hi] to be sorted.
A sorted half exposes its minimum and maximum at its two ends. If target fits inside that range, search that half; if not, the target can only live in the other half. Either way you discard half the window every step — which is all binary search ever needed.
| Linear scan | Sorted-half binary search | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
Full, runnable code for both approaches lives in the Approaches selector below.
Key takeaway
Binary search never required a fully sorted array — it requires a way to discard half the window with certainty. In a rotated sorted array, nums[lo] <= nums[mid] always exposes a sorted half, and that half's endpoints tell you exactly which side to keep.
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1