Skip to main content

22. Search in Rotated Sorted Array

mediumAsked at Udemy

Binary search in a rotated sorted array — Udemy uses this to evaluate whether candidates can adapt standard binary search for marketplace catalog lookups with shifted indices.

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

Problem

There is an integer array nums sorted in ascending order that has been rotated at an unknown pivot. Given the array and an integer target, return the index of target in nums or -1 if it is not present.

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i], target <= 10^4
  • All values of nums 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 until target is found — O(n), misses the O(log n) expectation.

Time
O(n)
Space
O(1)
function search(nums, target) {
  return nums.indexOf(target);
}

Tradeoff:

2. Modified binary search

At each midpoint, determine which half is sorted; check if target lies within that sorted half to decide which side to recurse into.

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:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

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

Practice these live with InterviewChamp.AI →