Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Salesforce

Search for a target in a rotated sorted array in O(log n). Salesforce uses this to test modified binary search — they value the 'figure out which half is sorted' reasoning.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this as a major-leagues binary-search test.
  • Blind (2025-12)— Common on Salesforce L4/L5 onsites.

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 left to right; return on match.

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

Tradeoff: O(n) violates the explicit O(log n) requirement.

2. Modified binary search

Mid-point splits the array into two halves; at least one is sorted. Check which, then check if target lies in that range; else search the other 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]) {
      if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Tradeoff: O(log n). The key insight: at any mid-point, comparing nums[lo] and nums[mid] tells you which half is sorted. Then range-check target.

Salesforce-specific tips

Salesforce grades on whether you articulate the invariant 'at every iteration, at least one half is sorted' BEFORE coding. Bonus signal: explain that the boundary checks `target >= nums[lo]` (not `>`) and `target <= nums[hi]` are critical to include the edge values.

Common mistakes

  • Using `nums[lo] < nums[mid]` instead of `<=` — fails on size-2 arrays where lo == mid.
  • Using `target > nums[lo]` instead of `>=` — misses target == nums[lo].
  • Not handling duplicates — this problem has unique values but LC 81 generalizes to duplicates.

Follow-up questions

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

  • Search in Rotated Sorted Array II (LC 81) — allow duplicates (O(n) worst case).
  • Find Minimum in Rotated Sorted Array (LC 153).
  • Find Peak Element (LC 162).

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

The original array is sorted; a single rotation splits it into two sorted halves with one 'discontinuity'. The mid-point lands in one half, so the OTHER side of mid is entirely within one half and thus sorted.

What if duplicates are allowed?

LC 81. With duplicates, nums[lo] == nums[mid] is ambiguous (could be left-sorted or both equal). Worst case degrades to O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →