Coding Interview PatternsSearch in Rotated Sorted Array
MediumModified Binary Search

Search in Rotated Sorted Array

Explanation & Solution

Practice Problem

Description

Given an integer array nums sorted in ascending order with distinct values, which is possibly rotated at an unknown pivot index, and an integer target, 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.

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

Output: 4

Explanation: 0 is found at index 4.

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

Approach

Modified Binary Search pattern

1. Initialize Two Pointers

  • Set left = 0 and right = nums.length - 1.

2. Modified Binary Search

  • Compute mid = (left + right) >> 1.
  • If nums[mid] === target, return mid.

3. Determine Which Half Is Sorted

  • If nums[left] <= nums[mid], the left half is sorted.
  • If target falls within [nums[left], nums[mid]), search left: right = mid - 1.
  • Otherwise, search right: left = mid + 1.
  • Else, the right half is sorted.
  • If target falls within (nums[mid], nums[right]], search right: left = mid + 1.
  • Otherwise, search left: right = mid - 1.

4. Return -1 If Not Found

  • If the loop ends, the target is not in the array.

🧠 Key Insight

  • The key insight is that in a rotated sorted array, at least one half is always sorted. By identifying the sorted half, we can determine which side the target must be in.
Time
O(log n)each step eliminates half the search space.
Space
O(1).

Visualization

Input:
[4, 5, 6, 7, 0, 1, 2], target = 0
40516273041526
—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone
8 steps

Solution Code

Previous
Binary Search
Next
Search in Rotated Sorted Array II