Search in Rotated Sorted Array: Crack This Classic Binary Search Interview Problem

Search in Rotated Sorted Array: Crack This Classic Binary Search Interview Problem | DevMentor

🧩 The Problem — And Why Interviewers Love It#

Here's the setup: you're given a sorted array that's been rotated at some unknown pivot point, and you need to find a target value. Return its index, or -1 if it doesn't exist.

text

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

This shows up constantly at FAANG interviews — and here's why interviewers reach for it: it's not enough to memorize binary search. You have to adapt it. That's exactly the signal they're hunting for. Can you take a known pattern and apply it to a messier, real-world-ish constraint? That's what separates a strong candidate from someone who just crammed LeetCode.

When I was coaching a candidate preparing for their Google loop last year, this was the exact problem that tripped them up in a mock session. Not because they didn't know binary search — they absolutely did. They panicked because the array "wasn't normal." Let's make sure that doesn't happen to you.

🔍 What the Interviewer Is Really Testing#

Before we touch any code, let's talk about what's actually being evaluated here.

The interviewer is checking whether you can:

Recognize that a modified binary search is applicable (not just defaulting to linear scan)
Identify the key invariant: at least one half of the array is always sorted
Handle boundary conditions carefully without getting sloppy with comparisons
Communicate your reasoning step by step, not just produce correct code in silence

A strong answer: candidate immediately observes the rotation doesn't break binary search entirely, articulates the "one half is always sorted" insight unprompted, and writes clean code with correct boundary conditions on the first try.

A weak answer: candidate stares at the problem, says "it's not sorted so I guess O(n)?" or jumps straight to code without explaining their approach. Even if the code works, silence during a binary search problem is a yellow flag.

💡 The Core Insight — Don't Skip This#

Here's the thing most people miss: they see a rotated array and think "the sorting is broken, binary search won't work." That's the wrong mental model.

The rotation doesn't destroy all the sorted structure — it just splits it. At any mid point you pick:

One of the two halves will always be perfectly sorted.

That's your anchor. You don't need to find the pivot explicitly. You don't need a two-pass approach. You just need to:

Find mid
Figure out which half is sorted
Check if your target lives in that sorted half
Eliminate the half that can't contain the target

Every iteration cuts the search space in half. That's your O(log n) right there.

🧠 The Approach, Step by Step#

Let's walk through the logic before looking at code, because understanding why each line exists will help you reconstruct this under pressure.

Step 1: Set l = 0, r = nums.length - 1. Standard binary search setup.

Step 2: While l <= r, compute mid = l + (r - l) / 2. The l + (r - l) / 2 form avoids integer overflow — mention this to your interviewer, it's a small detail that signals experience.

Step 3: If nums[mid] == target, you're done. Return mid.

Step 4: Determine which half is sorted:

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

Step 5: Check if the target falls within the sorted half's range:

Left sorted: is nums[l] <= target < nums[mid]? If yes, search left. Otherwise, go right.
Right sorted: is nums[mid] < target <= nums[r]? If yes, search right. Otherwise, go left.

Step 6: If the loop exits without finding the target, return -1.

✅ The Code#

java

class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
 
        while (l <= r) {
            int mid = l + (r - l) / 2;
 
            if (nums[mid] == target) {
                return mid;
            }
 
            // Left half is sorted
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target &&

Here's the same logic in Python if that's your language of choice:

python

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
 
    while l <= r:
        mid = l + (r - l) // 2
 
        if nums[mid] == target:
            return mid
 
        # Left half is sorted
        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid

🧪 Dry Run — Walk Through It Live#

Let's trace through nums = [4,5,6,7,0,1,2], target = 0.

Iteration	l	r	mid	nums[mid]	Action
1	0	6	3	7	Left [4,5,6,7] sorted. 0 not in [4,7). Go right → l=4
2	4	6	5	1	Right [1,2] sorted. 0 not in (1,2]. Go left → r=4
3	4	4	4	0	Match! Return 4

Notice how each step confidently eliminates half the array. That's the story you want to tell your interviewer — "I always know which half to eliminate, and here's why."

⚠️ Where Candidates Get Stuck#

This is the section that'll save you. These are the exact failure modes I see over and over again.

Mistake 1: Using `l < r` instead of `l <= r`#

This skips the single-element case. If your target happens to be the last remaining element after all the eliminations, l == r, and l < r exits early without checking it. You return -1 when the answer is right there. Always use l <= r.

Mistake 2: Strict less-than when detecting the sorted half#

java

// ❌ This breaks on small arrays like [3, 1]
if (nums[l] < nums[mid])
 
// ✅ Use <=
if (nums[l] <= nums[mid])

When the array has two elements and l == mid, strict < fails. The <= handles the edge case where mid equals l.

Mistake 3: Sloppy boundary conditions in range checks#

I've seen candidates write something like this in a panic:

java

// ❌ Not valid Java/Python syntax, and logically ambiguous
if (nums[l] < target < nums[mid])

Always be explicit:

java

// ✅ Clear, unambiguous
if (nums[l] <= target && target < nums[mid])

Think carefully about whether each comparison should be < or <=. The target can equal nums[l], but nums[mid] is already handled by the early return above it.

Mistake 4: Hunting for the pivot first#

A common trap is thinking, "I'll find the rotation point first, then do binary search on each half." That's two passes, more complex code, and unnecessary. The single-pass approach above handles everything in one loop. If you go down the pivot-hunting road in an interview, you're writing more code and introducing more bugs. Keep it simple.

Mistake 5: Not handling duplicates (follow-up trap)#

The standard problem guarantees no duplicates. But a common follow-up is "what if duplicates are allowed?" (LeetCode 81). The key difference: when nums[l] == nums[mid], you can't determine which half is sorted, so you have to do l++ and shrink the window one step at a time. Worst case becomes O(n). Know this going in.

🗣️ How to Talk Through This in an Interview#

Your verbal communication is half the evaluation. Here's exactly how I'd coach you to walk through this:

Opening (after reading the problem):

"Okay, so the array is sorted but rotated at some pivot. My first instinct is binary search since we need O(log n). The rotation complicates it, but here's the key observation: at any midpoint, one of the two halves has to be fully sorted. So I can still use binary search — I just need to figure out which half is sorted and whether my target falls in that range."

While coding:

"I'm using l <= r here because I want to check the single-element case. And for detecting the sorted half, I'll use nums[l] <= nums[mid] — the <= handles the edge case where l and mid are the same index."

After coding, proactively:

"Let me trace through the first example to verify... [walk through the dry run]. And I should think about edge cases: empty array — the while loop just never runs, so we return -1. Single element — l == r == mid, we check it directly. Target at the boundaries — handled by the <= comparisons."

This kind of narration shows the interviewer you understand why your code works, not just that it works.

🔄 Follow-Up Questions — Be Ready#

Interviewers almost always have a follow-up queued up. Here's what to expect and how to handle it:

"What's your time and space complexity?" Easy: O(log n) time because we halve the search space each iteration. O(1) space — pure iterative, no recursion or auxiliary data structures.

"What if the array has duplicates?" (LeetCode 81) This is the real test. When nums[l] == nums[mid], you can't tell which half is sorted. Your only safe move is l++. Worst case degrades to O(n), but average case is still much better.

"Can you find the rotation index (the minimum element)?" (LeetCode 153) Same family of problems. Modified binary search: if nums[mid] > nums[r], the minimum is in the right half. Otherwise it's in the left (including mid). Connects directly to this problem.

"What if you need to search in a rotated array with no information — not even the length?" Rare, but shows up occasionally. You'd need to first find the bounds using exponential search, then apply this approach.

🚩 Red Flags to Avoid#

Jumping to code immediately without explaining your approach. Even 60 seconds of verbal framing makes a huge difference.
Not asking about constraints — "Can the array be empty? Can there be duplicates?" shows you think about edge cases.
Silent debugging — if your first attempt has a bug, talk through how you're finding it. "Let me trace through this case... ah, I see, when l == mid this condition fails. Let me fix the comparison to <=."
Giving up on binary search when you see the rotation. This is exactly the moment interviewers want to see you push through the discomfort and adapt.
Magic numbers and unexplained conditions — every <= vs < decision should be something you can defend if asked.

⏱️ Complexity Summary#

Metric	Value	Reason
Time	O(log n)	Search space halves each iteration
Space	O(1)	Iterative, no extra data structures
Worst case (no dupes)	O(log n)	Guaranteed halving
Worst case (with dupes)	O(n)	May need to increment `l` one at a time

🎯 Key Takeaways#

Here's what to burn into memory before your next interview:

The invariant: one half is always sorted — this is the entire foundation of the solution
Always use l <= r to avoid missing the single-element case
Always use <= when detecting sorted half (nums[l] <= nums[mid]) to handle l == mid
Write boundary conditions explicitly — no chained comparisons, no shortcuts
Don't look for the pivot — you don't need it, and chasing it adds complexity and bugs
Know the follow-up: duplicates force worst-case O(n), and you should be able to explain why
Talk through your reasoning — interviewers want to hear the invariant out loud, not just see correct code

This problem is genuinely one of the best binary search problems to master because it teaches you to work with partial structure rather than perfect structure. Once you internalize the "one half is always sorted" insight, a whole family of rotated array problems opens up. Nail this one, and you'll recognize the pattern every time it shows up dressed in different clothes.

🧩 The Problem — And Why Interviewers Love It#

🔍 What the Interviewer Is Really Testing#

💡 The Core Insight — Don't Skip This#

🧠 The Approach, Step by Step#

✅ The Code#

🧪 Dry Run — Walk Through It Live#

⚠️ Where Candidates Get Stuck#

Mistake 1: Using l < r instead of l <= r#

Mistake 2: Strict less-than when detecting the sorted half#

Mistake 3: Sloppy boundary conditions in range checks#

Mistake 4: Hunting for the pivot first#

Mistake 5: Not handling duplicates (follow-up trap)#

🗣️ How to Talk Through This in an Interview#

🔄 Follow-Up Questions — Be Ready#

🚩 Red Flags to Avoid#

⏱️ Complexity Summary#

🎯 Key Takeaways#

Mistake 1: Using `l < r` instead of `l <= r`#