Skip to main content

20. Search in Rotated Sorted Array

mediumAsked at Coupang

Find a target in a rotated sorted array in O(log n), mirroring how Coupang's same-day delivery routing locates a slot in a partially rotated time-window index after midnight pivot.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is an integer array nums sorted in ascending order, then possibly rotated at an unknown pivot. Given a target value, return its index or -1 if absent. You must run in O(log n).

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i], target <= 10^4
  • all values are unique

Examples

Example 1

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

Example 2

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

Approaches

1. Linear scan

Walk the array.

Time
O(n)
Space
O(1)
for (let i = 0; i < nums.length; i++) if (nums[i] === target) return i;
return -1;

Tradeoff:

2. Modified binary search

At each midpoint, one side is sorted; check if target is within that sorted side and bisect accordingly.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (nums[m] === target) return m;
    if (nums[l] <= nums[m]) {
      if (target >= nums[l] && target < nums[m]) r = m - 1;
      else l = m + 1;
    } else {
      if (target > nums[m] && target <= nums[r]) l = m + 1;
      else r = m - 1;
    }
  }
  return -1;
}

Tradeoff:

Coupang-specific tips

Coupang's same-day delivery routing locates slots in a time-window index that rotates at midnight; modified binary search is the standard pattern in their dispatcher's slot-lookup hot path.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Search in Rotated Sorted Array and other Coupang interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →