Skip to main content

21. Search in Rotated Sorted Array

mediumAsked at Gojek

Search for a target in a sorted array that has been rotated around some pivot, in logarithmic time.

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

Problem

There is an integer array nums sorted in ascending order with distinct values. The array was rotated at an unknown pivot. Given the rotated array and a target value, return the index of the target, or -1 if it is not present. You must write an algorithm with O(log n) runtime.

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 and compare each element to target.

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 identify which half is sorted, then check whether the target lies in that sorted half and recurse there. The other half is rotated and handled recursively.

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 (nums[l] <= target && target < nums[m]) r = m - 1; else l = m + 1;
    } else {
      if (nums[m] < target && target <= nums[r]) l = m + 1; else r = m - 1;
    }
  }
  return -1;
}

Tradeoff:

Gojek-specific tips

Gojek expects you to verbalize the invariant on which half is sorted, because rotated-log scans show up in their region-partitioned dispatcher indexes.

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 Gojek interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →