Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Workday

Search a target in a sorted-then-rotated array in O(log n). Workday uses this to test modified binary search — same shape as querying a payroll-cycle log that has been wrapped around midnight.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite — binary-search variant.

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 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 compare.

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

Tradeoff: Violates the O(log n) requirement.

2. Modified binary search

At each mid, determine which half is sorted. Decide whether target lies in the sorted 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]) {
      // left half sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // right half sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Tradeoff: Key insight: at any split point, at least one half is sorted (because the rotation is contiguous). Determine which, then decide if target is in that half.

Workday-specific tips

Workday grades on the 'which half is sorted' decision. The condition nums[lo] <= nums[mid] is what tells you — get the <= right (with equality handles the trivial 'single element' case). Walk through with [4,5,6,7,0,1,2] before coding.

Common mistakes

  • Comparing nums[mid] to nums[hi] instead of nums[lo] — works too but requires different boundary checks.
  • Using < instead of <= for the sorted-half test — fails when lo == mid.
  • Wrong direction for the second half's check.

Follow-up questions

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

  • Search in Rotated Sorted Array II (LC 81) — duplicates allowed.
  • Find Minimum in Rotated Sorted Array (LC 153).
  • What if rotated multiple times?

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

The original array is sorted, then rotated once. Splitting it at any mid produces at most one 'wrap' boundary — so at least one half avoids it and is fully sorted.

Why nums[lo] <= nums[mid] (not <)?

When lo == mid (single element), nums[lo] == nums[mid]. Using strict < would incorrectly classify this case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →