📖 10 min read
Last updated on

Search in Rotated Sorted Array — Coding Interview Walkthrough

By intervu.dev

Hero Image for Search In Rotated Sorted Array

You’re in a coding interview. The interviewer gives you a sorted array that’s been rotated at some unknown pivot and asks you to find a target in O(log n) time. You know it’s binary search, but the array isn’t cleanly sorted anymore. Which half do you eliminate? How do you know which side the target is on when the values wrap around? The boundary conditions that feel trivial in a textbook become treacherous when someone is watching you reason through them live.

This walkthrough covers how that conversation unfolds: the structural observation that makes adapted binary search possible, the exact comparisons that trip up experienced engineers, and the follow-up about duplicates that changes the problem entirely.

The Problem

You are given an integer array nums sorted in ascending order, which has been rotated at some unknown pivot index. For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] after rotating at index 3.

Given nums and an integer target, return the index of target if it exists in the array, or -1 if it does not. Your solution must run in O(log n) time.

(LeetCode #33)

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

In Example 1, the array was originally [0, 1, 2, 4, 5, 6, 7] and was rotated so that 4 is now at index 0. Target 0 is found at index 4. In Example 2, 3 simply doesn’t exist in the array. The key structural observation is that even after rotation, at least one half of the array, when you pick a midpoint, is always guaranteed to be sorted. That guarantee is what makes O(log n) possible.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

This problem isn’t about memorizing a rotated binary search template. It’s about whether you can reason through a modified invariant and adapt a well-known algorithm without losing your footing.

SkillWhat Interviewers Observe
Binary search fundamentalsDo you understand why binary search works, not just how to write it?
Invariant reasoningCan you identify which half is sorted at every midpoint, and use that to eliminate half the array?
Boundary condition precisionDo you get <= vs <, and mid + 1 vs mid exactly right without trial and error?
Edge case awarenessDo you handle single-element arrays, target at pivot, and target not present?
Communication under pressureCan you walk through your decision logic step by step before writing code?

Step 1: Clarifying Questions

These questions take under a minute to ask and demonstrate the kind of precision that stands out.

1. Are all values in the array distinct? The standard version of this problem guarantees unique elements. If duplicates are allowed (as in LeetCode #81), the algorithm changes meaningfully: you can no longer determine which half is sorted just by comparing endpoints. Confirming this scopes the problem correctly.

2. Can the array have just one element? Yes, and your algorithm should handle it. nums = [5], target = 5 should return 0, and nums = [5], target = 3 should return -1.

3. Is it guaranteed that the array has been rotated, or could it be fully sorted? A fully sorted array is a valid rotation (rotated by 0). Your algorithm should handle this without special-casing it, and confirming this tells you not to assume a pivot always exists.

4. Should I return the index or just a boolean? The problem asks for the index, but confirming this prevents you from building toward the wrong return type.

5. Are there constraints on the size of nums? Knowing the upper bound (up to 5,000 elements) confirms that O(log n) is expected, not just preferred.

Step 2: A First (Non-Optimal) Idea

The simplest approach is a linear scan: iterate through every element and return the index when you find the target.

def search_linear(nums, target):
    for i, val in enumerate(nums):
        if val == target:
            return i
    return -1
ApproachTimeSpace
Linear scanO(n)O(1)
Find pivot + two binary searchesO(log n)O(1)

This is correct and runs in O(n) time. For small arrays it’s fine, but it completely ignores the sorted structure, and the problem explicitly requires O(log n).

A slightly smarter but unnecessarily complex direction: find the pivot first, then run two separate binary searches. This works but adds extra passes and logic. The cleaner insight eliminates this entirely.

Step 3: The Key Insight

Even in a rotated sorted array, when you pick any midpoint, at least one of the two halves is always fully sorted. The rotation creates at most one break point. If nums[left] <= nums[mid], the left half is sorted. Otherwise, the right half is sorted. Once you know which half is sorted, you can check whether the target falls within that sorted range. If it does, search there. If not, search the other half. Either way, you eliminate half the array at each step.

Think about why. The rotation creates at most one “break point” in the array where the values drop. A midpoint either falls in the ascending left portion or the ascending right portion. It can’t fall in both at the same time. So:

  • If nums[left] <= nums[mid], the left half [left, mid] is sorted.
  • Otherwise, the right half [mid, right] is sorted.

Once you know which half is sorted, you can check whether the target falls within that sorted range using simple comparisons against its endpoints. If it does, search that half. If it doesn’t, search the other half. Either way, you eliminate half the array, exactly like standard binary search.

Rotated array [4,5,6,7,0,1,2] with sorted left half [4,5,6,7] in blue, lo/mid/hi pointers, and target 0 found at index 4. ---

Step 4: Optimal Strategy

  1. Initialize left = 0 and right = len(nums) - 1.
  2. Enter a while left <= right loop.
  3. Compute mid = (left + right) // 2.
  4. If nums[mid] == target, return mid.
  5. Determine which half is sorted:
    • If nums[left] <= nums[mid], the left half is sorted.
      • If nums[left] <= target < nums[mid], the target is in the left half → set right = mid - 1.
      • Otherwise, the target must be in the right half → set left = mid + 1.
    • Otherwise, the right half is sorted.
      • If nums[mid] < target <= nums[right], the target is in the right half → set left = mid + 1.
      • Otherwise, the target must be in the left half → set right = mid - 1.
  6. If the loop exits without finding the target, return -1.

Python Implementation

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Determine which half is guaranteed to be sorted
        if nums[left] <= nums[mid]:
            # Left half [left, mid] is sorted
            if nums[left] <= target < nums[mid]:
                # Target falls within the sorted left range
                right = mid - 1
            else:
                # Target must be in the right half
                left = mid + 1
        else:
            # Right half [mid, right] is sorted
            if nums[mid] < target <= nums[right]:
                # Target falls within the sorted right range
                left = mid + 1
            else:
                # Target must be in the left half
                right = mid - 1

    return -1  # Target not found

Let’s trace through Example 1: nums = [4, 5, 6, 7, 0, 1, 2], target = 0

  • left=0, right=6 → mid=3, nums[3]=7, not target
    • nums[0]=4 <= nums[3]=7 → left half [4,5,6,7] is sorted
    • Is 4 <= 0 < 7? No → search right half → left = 4
  • left=4, right=6 → mid=5, nums[5]=1, not target
    • nums[4]=0 <= nums[5]=1 → left half [0,1] is sorted
    • Is 0 <= 0 < 1? Yes → search left half → right = 4
  • left=4, right=4 → mid=4, nums[4]=0 → found! return 4 ✓

Time & Space Complexity

AspectComplexityExplanation
TimeO(log n)Each iteration eliminates half the remaining array
SpaceO(1)Only pointer variables, no auxiliary data structures

Time: The rotation doesn’t change the fundamental O(log n) guarantee because we still eliminate exactly half the search space at every step. We’ve simply added logic to determine which half to eliminate.

Space: Only three integer variables (left, right, mid). No recursion, no auxiliary data structures.

Common Interview Mistakes

  1. Using < instead of <= when checking if the left half is sorted. The condition nums[left] <= nums[mid] uses <=, not <. This matters when left == mid (single element remaining on the left). Using strict < would misclassify that case and send the search in the wrong direction.

  2. Getting the target range check wrong. When checking if the target is in the sorted left half, the condition is nums[left] <= target < nums[mid], strict less-than on the right because mid itself was already checked. Flipping any of these operators silently produces wrong answers on edge cases.

  3. Trying to find the pivot first. Some candidates spend time writing a separate function to locate the rotation point, then run two binary searches. This works but is more complex and easier to get wrong. The one-pass approach is cleaner and directly demonstrates the core insight.

  4. Not handling the non-rotated case. If the array was never rotated (e.g., [1, 2, 3, 4, 5]), nums[left] <= nums[mid] is always true and the algorithm correctly reduces to standard binary search. Candidates who hardcode assumptions about a pivot always existing will fail this case.

  5. Off-by-one on pointer updates. When you’ve confirmed the target is NOT in the sorted half, you move to the other side using left = mid + 1 or right = mid - 1, not left = mid or right = mid. Forgetting the ±1 creates an infinite loop when the target is adjacent to the midpoint.

  6. Coding before drawing an example. The decision logic in this problem is dense. Candidates who code immediately, without first walking through a concrete rotated array, frequently write conditions they haven’t verified. Spending 60 seconds tracing through [4,5,6,7,0,1,2] with target=0 before writing a line of code prevents most bugs.

  7. Forgetting to handle target == nums[mid] before the half-determination logic. This check must come first. If you defer it, you risk updating left or right past the answer before you check it.

What a Strong Candidate Sounds Like

“My first observation is that even though the array is rotated, picking any midpoint always leaves at least one half that’s cleanly sorted. If nums[left] <= nums[mid], the left half is sorted. I know its exact range, so I can immediately tell whether the target falls inside it. If yes, I go left. If no, I go right. Same logic applies when the right half is sorted. I’m still eliminating half the array at each step, so I keep the O(log n) guarantee. The rotation just means I need one extra check to figure out which half is the sorted one before I decide where to go. Let me trace through the example to make sure my boundary conditions are right before I write the code.”

This response shows: the invariant was reasoned through, not memorized; the candidate thought about both halves; they proactively traced before coding.

Example Interview Dialogue

Interviewer: What if the array isn’t rotated at all, like [1, 2, 3, 4, 5]?

Candidate: The algorithm handles it naturally. If the array is fully sorted, nums[left] <= nums[mid] will always be true, so the left half is always identified as sorted. From there, the target range check behaves exactly like standard binary search. No special-casing needed.

Interviewer: What if there are duplicate values in the array?

Candidate: That’s where it gets tricky. With duplicates, you can hit a situation where nums[left] == nums[mid] == nums[right], and you genuinely can’t tell which half is sorted just from the endpoints. In that case, you have to fall back to incrementing left and decrementing right by one, which degrades worst-case time to O(n). That’s the problem LeetCode #81 covers, Search in Rotated Sorted Array II.

Interviewer: Can you find the rotation index instead, and use that?

Candidate: Yes. You can binary search for the pivot (the index where nums[i] > nums[i+1]), then determine which sorted subarray the target belongs to and run standard binary search on that half. It’s two passes instead of one, but both are O(log n) so the overall complexity stays the same. I’d still prefer the single-pass approach here since it’s more concise, but the two-pass approach is easier to reason about if you’re prone to mixing up the boundary conditions.

Search in Rotated Sorted Array is the entry point to the “binary search on non-standard invariants” family. These problems all require adapting binary search to structures that aren’t cleanly sorted:

From the Intervu walkthrough collection:

Practice This in a Mock Interview

Reading this explanation gives you the mental model, but the boundary conditions in this problem are notoriously easy to get subtly wrong under pressure. The difference between < and <=, between mid and mid - 1, between checking left-sorted vs right-sorted first: any one of these can silently break your solution in ways that only show up on specific edge cases.

In a real interview, you won’t have the luxury of re-reading this walkthrough when you second-guess yourself. The only way to make these conditions feel automatic is to practice them repeatedly, out loud, with someone watching.

Start a mock interview for Search in Rotated Sorted Array on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →