Search in Rotated Sorted Array

Problem in Plain English

You are given a rotated sorted array of distinct integers and a target value. Return the index of the target in the array, or negative one when the target is absent.

Problem Statement

There is an integer array nums sorted in ascending order with distinct values. Before it reaches you, nums is possibly rotated at an unknown pivot index, so the tail of the sorted order may wrap to the front.

Given the possibly rotated array nums and an integer target, return the index of target if it is in nums, or -1 if it is not. The required solution runs in $O(log n)$ time.

Constraints

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

Examples

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

The value 0 sits at index 4, so the answer is 4.

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

The target 3 lies in the gap between 2 and 4 in the original sorted order. Rotation changes positions but adds no values, so the candidate interval eventually becomes empty and the answer is -1.

Example 3

Input: nums = [1], target = 0
Output: -1

The single element 1 is not the target, so the answer is -1.

Example 4

Input: nums = [3,1], target = 1
Output: 1

The midpoint is initially index 0. Its one-element left half is sorted, but target 1 is outside it, so the search retains index 1 and finds the match. This exercises inclusive half detection on two elements.

Intuition

Rotation cuts one ascending sequence into two ascending pieces and swaps their order. In Example 1, [4,5,6,7] is followed by [0,1,2], so comparing only the midpoint 7 with target 0 does not tell us which side to keep. At each midpoint, however, at least one half has no wrap and is sorted. Its endpoints tell us whether target belongs in that half; otherwise we keep the other half.

Approaches

Linear Scan

Solution Details

Reveal Linear Scan: intuition, complexity, and code

Intuition

Compare the target with each position in order and return the first matching index. Rotation has no effect on this exhaustive search, but finding the final value or proving absence costs a full pass.

Step-by-Step Logic

Start index i at 0 and compare nums[i] with target. In Example 1 target is 0 and the first comparison is 4 != 0.
After a mismatch increment i by one. The next comparisons visit index 1 holding 5, index 2 holding 6 and index 3 holding 7.
Return the current index immediately on equality. At i = 4, nums[4] equals 0, so return 4.
If i reaches nums.length without equality, return -1 because every position has been checked.

Why It Works

At the start of iteration i, every index below i has been checked and is unequal to target. Inspecting nums[i] extends this invariant after a mismatch; an equality returns an index that actually holds target. If the loop finishes, the invariant covers the entire array, so target is absent. Distinct values make the matching index unique.

Dry Run

Linear Scan: variable states at each step
i before	nums[i]	comparison	transition / result
0	4	mismatch	i 0 to 1
1	5	mismatch	i 1 to 2
2	6	mismatch	i 2 to 3
3	7	mismatch	i 3 to 4
4	0	equality	return 4; i remains 4

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Let n be the array length. An absent target or a match at the final index requires n comparisons, so worst-case time is O(n). The loop stores one index and returns one integer; no copied array, map, slices or recursion is allocated. Auxiliary space is O(1).

Code

Solution.java

1class Solution {2    public int search(int[] nums, int target) {3        for (int i = 0; i < nums.length; i++) {4            if (nums[i] == target) {5                return i;6            }7        }8        return -1;9    }10}

Hints

Hint 1

Split any interval at mid: at least one of the two halves must be in sorted order, so test it with nums[left] <= nums[mid].

Hint 2

Once the sorted half is known, check whether target sits between its endpoints before deciding which half to drop.

Hint 3

Keep the left <= right loop with mid - 1 and mid + 1 updates so a single remaining element is still examined.

Edge Cases

A single-element array such as [1] with a missing target returns -1 after one comparison.
An unrotated array behaves like plain binary search because the left half is sorted every time.
A target sitting exactly at the rotation dip, like 0 in [4,5,6,7,0,1,2], is found once the interval narrows to it.
Two elements with rotation, such as [3,1], require treating left == mid as a sorted one-element half.
Targets at either endpoint must remain eligible: the sorted-half range includes nums[left] or nums[right], while mid was already checked for equality.
Negative values and zero affect comparisons only; the same half-detection rule applies.

Common Mistakes and Interview Tips

Testing whether the target is in range before confirming which half is sorted, which discards the wrong side.
Using strict < instead of <= for the sorted-half test, which misclassifies a one-element half.
Updating bounds with mid instead of mid - 1 or mid + 1, which can loop forever on two elements.
Sorting the input before searching changes the indices you are asked to return and costs O(n log n) time.
Using ordinary binary search solely from nums[mid] < target ignores the rotation and can discard a present target.
Excluding the endpoint in nums[left] <= target or target <= nums[right] loses matches at the retained half's boundary.
Reusing this distinct-value algorithm for duplicate input such as [1,0,1,1,1] can hide the pivot; equal endpoints require additional handling.

Key Takeaway

When rotation breaks global order, identify the sorted half of each interval and keep only the side that can still hold the target.