Skip to main content

15. Search in Rotated Sorted Array

mediumAsked at Swiggy

Binary search a target in a sorted array that has been rotated at an unknown pivot.

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

Problem

An integer array nums was sorted ascending and then rotated at some pivot. Given the rotated array and a target, return the index of target or -1. Solve in O(log n) time.

Constraints

  • 1 <= nums.length <= 5000
  • All values unique
  • -10^4 <= nums[i] <= 10^4

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 step one half is guaranteed sorted (compare nums[lo] and nums[mid]). Check if the target lies in that sorted half; if yes, recurse there, otherwise recurse the other half.

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

Tradeoff:

Swiggy-specific tips

Swiggy uses rotated search to probe whether you can spot the sorted half — the same reasoning shows up in their cyclic restaurant-availability 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 Swiggy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →