Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Ola

Search for a target in a rotated sorted array in O(log n).

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

Problem

Given a sorted integer array nums that may have been rotated at an unknown pivot, 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.

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 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

Iterate the array and return the index.

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

Tradeoff:

2. Binary search with side check

Each midpoint splits into one sorted half; pick the half containing target by checking endpoints.

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:

Ola-specific tips

Ola probes rotated-binary-search bookkeeping; tie it to locating a target ETA bucket in a wrap-around hourly-demand window.

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

Practice these live with InterviewChamp.AI →