Skip to main content

33. Search in Rotated Sorted Array

mediumAsked at eBay

eBay's inventory system maintains sorted product ID ranges that can be 'rotated' after a shard rebalancing. Search in Rotated Sorted Array is the binary search variant eBay uses to test whether candidates can maintain the O(log n) invariant even when the sort order is disrupted. Correctly identifying which half is sorted is the key insight.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-12)— Cited as a common eBay medium binary search problem in onsite rounds, testing binary search extension skills.
  • Blind (2025-10)— eBay SWE threads list this as a standard mid-level binary search question, often following a plain binary search warm-up.

Problem

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not.

Constraints

  • 1 <= nums.length <= 5000
  • −10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • −10^4 <= target <= 10^4

Examples

Example 1

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

Explanation: The array is rotated. The left half [4,5,6,7] is sorted; the target 0 is not in range [4,7], so search the right half [0,1,2].

Example 2

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

Explanation: Target 3 is not in the array.

Example 3

Input
nums = [1], target = 0
Output
-1

Explanation: Single element; target not found.

Approaches

1. Modified Binary Search

At each step, determine which half is sorted. If the left half is sorted (nums[left] <= nums[mid]), check if target is in that range; if yes, search left; otherwise search right. Mirror for when the right half is sorted.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    // Determine which half is sorted
    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1; // target in left sorted half
      } else {
        left = mid + 1; // target in right half
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1; // target in right sorted half
      } else {
        right = mid - 1; // target in left half
      }
    }
  }
  return -1;
}

Tradeoff: O(log n) time, O(1) space. The key invariant: exactly one of the two halves is always sorted after a rotation. Use that sorted half's range to decide which side to search.

eBay-specific tips

eBay interviewers probe the boundary conditions: 'What does nums[left] <= nums[mid] tell you?' (Left half is sorted — strictly, nums[left] <= nums[mid] includes the non-rotated case where both halves are sorted.) Draw a few examples: [4,5,6,7,0,1,2] with mid=6(index 3): nums[0]=4 <= nums[3]=7, left sorted. Walk through the target-in-range check out loud. Expect the follow-up: 'What if duplicates are allowed?' (LC 81 — worst case becomes O(n) due to left == mid == right ambiguity).

Common mistakes

  • Using strict < instead of <= in the sorted-half range check — misses the case where target equals nums[left] (boundary).
  • Forgetting that when nums[left] <= nums[mid], the left half is sorted (not the right) — swapping the halves inverts all subsequent logic.
  • Integer overflow in mid computation — use left + Math.floor((right - left) / 2) to be safe (matters in Java/C++ with int).
  • Not returning -1 when the while loop exits — missing the not-found case.

Follow-up questions

An interviewer at eBay may pivot to one of these next:

  • Search in Rotated Sorted Array II (LC 81) — allows duplicates; worst case degrades to O(n).
  • Find Minimum in Rotated Sorted Array (LC 153) — find the rotation pivot; similar binary search structure.
  • How would you first find the pivot index and then run two standard binary searches? (Alternative approach)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is nums[left] <= nums[mid] (not <) the check for a sorted left half?

When left == mid (single element range), nums[left] == nums[mid] is true. We classify this as 'left sorted' to avoid an infinite loop. Using < would incorrectly classify single-element ranges.

What happens if the array is not rotated at all?

nums[left] <= nums[mid] is always true (left half is always sorted in an unrotated array), and the algorithm degrades to standard binary search correctly.

Can I find the pivot first and then binary search each half?

Yes — find the rotation point in O(log n) first, then binary search the appropriate half. This uses the same O(log n) time but requires two passes. The single-pass approach above is more elegant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →