Search in Rotated Sorted Array

1. Define the problem

There is an integer array nums sorted in ascending order with distinct values, possibly rotated at an unknown pivot. Given the rotated array nums and a target value, return the index of target if it is in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity. At each midpoint, one half of the remaining range is always still sorted — check which half that is, then decide whether target can only be in the sorted half or must be in the other one.

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums_i ≤ 10⁴
All values of nums are unique
nums is an ascending array that was possibly rotated
-10⁴ ≤ target ≤ 10⁴

Example

Inputnums = [4, 5, 6, 7, 0, 1, 2], target = 0

Output4

Explanation The value 0 sits at index 4 in the rotated array.

2. Visualize the solution

Decide which half is sorted, then narrow toward the target

Statusinit

low=0, high=6, mid=3 (value 7). Left half [4..7] is sorted, but 0 is not inside it — search right.

What happens in this step

low=0, high=6
mid = 0 + floor((6-0)/2) = 3, nums[3] = 7

nums[low]=4 <= nums[mid]=7, so the left half [4..7] is sorted. Target 0 does not fall within [4, 7), so it must be in the right half — low becomes 4.

Step 1 of 3

Steps to visualize

The row is the whole rotated array; the box marks the part still being searched.
Compare nums_low to nums_mid to tell which half of the current range is sorted.
If the left half is sorted, check whether target falls inside that sorted range.
If it does, search the left half; otherwise search the right half.
If the right half is sorted instead, apply the same check on that side.
Repeat until nums_mid equals target, or low passes high.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Decide which half is sorted, then narrow toward the target

Statusinit

low=0, high=6, mid=3 (value 7). Left half [4..7] is sorted, but 0 is not inside it — search right.

What happens in this step

low=0, high=6
mid = 0 + floor((6-0)/2) = 3, nums[3] = 7

nums[low]=4 <= nums[mid]=7, so the left half [4..7] is sorted. Target 0 does not fall within [4, 7), so it must be in the right half — low becomes 4.

Step 1 of 3

4. Solution

Solution

solution.tsTypeScript

function search(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[low] <= nums[mid]) {
      if (nums[low] <= target && target < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }

  return -1;
}

Time: O(log n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [4, 5, 6, 7, 0, 1, 2], target = 0`	`4`	example from the docstring
`nums = [4, 5, 6, 7, 0, 1, 2], target = 3`	`-1`	target absent from the rotated array
`nums = [1], target = 1`	`0`	smallest valid input, target present
`nums = [1], target = 0`	`-1`	smallest valid input, target absent
`nums = [1, 2, 3, 4, 5], target = 3`	`2`	array with no rotation applied at all
`nums = [4, 5, 6, 7, 0, 1, 2], target = 4`	`0`	target is the first element of the sorted segment before the pivot
`nums = [4, 5, 6, 7, 0, 1, 2], target = 2`	`6`	target is the last element after the pivot
`nums = [3, 1], target = 1`	`1`	smallest rotated case, two elements

Search in Rotated Sorted Array