Search in Rotated Sorted Array Solution

Problem

An ascending-sorted array has been rotated at some unknown pivot, so what was [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Given the rotated array and a target value, return the index of the target, or -1 if it isn't there. All values are unique and the solution must run in O(log n) time.

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 appears at index 4 in the rotated array.

Counter-example:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 does not appear anywhere in the array.

Intuition

Splitting a rotated sorted array at any midpoint always leaves at least one half that is perfectly sorted. If you can identify which half is sorted, you can check whether the target falls within that half's range in O(1) — and if it doesn't, the target must be in the other half (or absent). Applying this observation at each step halves the search window, giving O(log n).

Approach 1 — Linear Scan

Scan every element from left to right and return the index the moment a match is found. Correct but does not exploit the sorted structure.

Iterate over every index from 0 to len(nums) - 1.
If the current element equals the target, return its index.
If the loop ends without a match, return -1.

1def search(nums: list[int], target: int) -> int:
2    for index, value in enumerate(nums):
3        if value == target:
4            return index
5    return -1

Time: O(n) — every element may need to be visited before finding the target or giving up. Space: O(1) — only a loop variable is used.

Approach 2 — Modified Binary Search

At each midpoint, one half of the current window must be sorted. Identify the sorted half, check whether the target lies within its range, then eliminate the other half — exactly like standard binary search but with one extra decision.

Initialize left = 0 and right = len(nums) - 1.
While left ≤ right, compute mid = (left + right) // 2.
If nums[mid] equals the target, return mid.
If nums[left] ≤ nums[mid], the left half [left..mid] is sorted.
- If nums[left] ≤ target < nums[mid], the target is in the left half: set right = mid - 1.
- Otherwise the target must be in the right half: set left = mid + 1.
Otherwise the right half [mid..right] is sorted.
- If nums[mid] < target ≤ nums[right], the target is in the right half: set left = mid + 1.
- Otherwise the target must be in the left half: set right = mid - 1.
Return -1 if the loop exits without finding the target.

1def search(nums: list[int], target: int) -> int:
2    left, right = 0, len(nums) - 1
3
4    while left <= right:
5        mid = (left + right) // 2
6
7        if nums[mid] == target:
8            return mid
9
10        if nums[left] <= nums[mid]:  # left half is sorted
11            if nums[left] <= target < nums[mid]:  # target falls inside the sorted left half
12                right = mid - 1
13            else:
14                left = mid + 1
15        else:  # right half is sorted
16            if nums[mid] < target <= nums[right]:  # target falls inside the sorted right half
17                left = mid + 1
18            else:
19                right = mid - 1
20
21    return -1

Time: O(log n) — the search window halves with every iteration. Space: O(1) — only left, right, and mid pointers are stored.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	Only for debugging or when O(log n) is not required
Modified Binary Search	O(log n)	O(1)	Any interview context; the only acceptable approach when O(log n) is required

Common Mistakes

Using < instead of <= for nums[left] <= nums[mid] — when left == mid (a one-element window), nums[left] == nums[mid], and the condition must still classify the left half as "sorted." Dropping the = misroutes the search on single- or two-element inputs.
Flipping the strict inequality on the range check — the test target < nums[mid] uses strict less-than because nums[mid] == target is already caught above; writing target <= nums[mid] causes the same index to be excluded and can produce infinite loops.
Missing <= on the right-side bound — when checking the right half, target <= nums[right] must be non-strict because the target could equal the last element; using < instead silently skips it.
Trying to decide direction without first identifying the sorted half — unlike regular binary search, you cannot simply compare target to nums[mid] to decide left or right. The rotation means both sides may contain values larger or smaller than nums[mid].
Confusing the rotation point handling — the smallest element sits at the join between the two ascending runs. The algorithm handles this naturally (it falls in the unsorted half and eventually becomes the sole element in its window), but conceptually ignoring the rotation point leads to wrong range comparisons.

Search in Rotated Sorted Array — Solution