Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Datadog

Search for a target in a rotated sorted array in O(log n). Datadog asks this because their TSDB indexes can be rotated chunks (after compaction crosses a boundary), and bisect must still work correctly.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog backend onsite — direct TSDB analogy.
  • Blind (2025-11)— Recurring at Datadog.

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. 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 in nums. You must write an algorithm with O(log n) runtime complexity.

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

Example 2

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

Example 3

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

Approaches

1. Linear scan

Walk and check each.

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

Tradeoff: Doesn't meet the O(log n) constraint. Datadog will reject.

2. Modified binary search (optimal)

At each step, one half is guaranteed sorted. Identify which, then check if target is in its range; bisect accordingly.

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]) {
      // left half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // right half is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Tradeoff: Single binary search with sorted-half identification. Datadog-canonical pattern for indexed lookup on rotated TSDB chunks.

Datadog-specific tips

Datadog wants you to articulate the key insight: at every midpoint, ONE half is sorted (because the rotation pivot is on the other side). Identify the sorted half (compare nums[lo] to nums[mid]), then check whether the target is in its range. Without this framing, the code looks arbitrary.

Common mistakes

  • Mixing up < and <= in the range checks — easy to off-by-one when the target equals nums[lo] or nums[mid].
  • Forgetting to compare nums[lo] <= nums[mid] (not strict) — needed when lo == mid (length-1 half).
  • Trying to find the rotation pivot first, then binary search — works but two passes (still O(log n) but clumsier).

Follow-up questions

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

  • Search in Rotated Sorted Array II (LC 81) — with duplicates.
  • Find Minimum in Rotated Sorted Array (LC 153) — locate the pivot.
  • Datadog-style: bisect a rotated on-disk TSDB chunk for a timestamp.

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 one half always sorted?

If you bisect a rotated array, the pivot lies in one half. The other half contains a contiguous sorted segment of the original — so it's sorted.

What if duplicates exist?

LC 81 — the trick fails when nums[lo] === nums[mid] (can't tell which half is sorted). Increment lo and retry; worst case O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →