Loading…

mediumBinary SearchLC #33Asked very often

Search in Rotated Sorted Array

Q: How do you solve Search in Rotated Sorted Array using the Linear Scan (Baseline) approach?

When to use it: Mention only to set the O(n) bar you're beating — then move on quickly, since the prompt demands O(log n). Walk the array and return the first index whose value equals the target, else `-1`. **Why mention it.** It's a correctness anchor and a complexity to beat. **Why it's wrong here.** The prompt requires `O(log n)`; a scan ignores the structure (sorted, single rotation) that lets us halve the search. Time complexity: O(n). Space complexity: O(1).

LCPractice

Binary Search · 2 of 16 · 10 min

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 (0 <= k < nums.length) so that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

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.

You must write an algorithm with O(log n) runtime complexity.

In plain English

Take a sorted array and cut it once, swapping the two pieces — that's a rotation. The array now has one 'drop' (where the larger end meets the smaller start). Despite the drop, any midpoint splits the array such that one side is a contiguous sorted run. We use that to keep halving.

Examples

Example 1

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Note: Rotated at pivot 4. 0 sits at index 4.

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Note: 3 is not present.

Example 3

Input: nums = [1], target = 0
Output: -1
Note: Single element, not the target.

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
All values of nums are unique
nums is an ascending array possibly rotated
-10⁴ ≤ target ≤ 10⁴

Clarifying questions4First question: Are the values guaranteed distinct?Explore questions

Q1.Are the values guaranteed distinct?
Yes here. Duplicates (LeetCode 81) break the `nums[lo] <= nums[mid]` test when they're equal and force a worst-case O(n) fallback.
Q2.Could the array be un-rotated (rotated by 0 or n)?
Yes — k can be 0, which means a normal sorted array. The same code handles it: the left half is always detected as sorted.
Q3.Do I need to find the pivot index first?
No. Finding the pivot then searching is a valid two-pass O(log n) approach, but the one-pass 'which half is sorted' method is cleaner and what interviewers look for.
Q4.What do I return when the target is absent?
-1, same as standard binary search.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A sorted array rotated at an unknown pivot still has the property that at any mid, at least one of the two halves [lo, mid] or [mid, hi] is fully sorted. In one binary search, figure out which half is sorted, test whether the target falls inside that sorted half's value range, and discard the half that can't contain it. O(log n) time, O(1) space — no need to find the pivot first.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can adapt the binary-search invariant to a non-monotonic array by reasoning about which half stays sorted, instead of giving up and scanning linearly.

Where candidates slip

Comparing only nums[mid] to target (plain binary search) and ignoring rotation, or getting the boundary `<=` wrong so a target equal to nums[lo] or nums[hi] is dropped.

How to stand out

Explain *why* one half is always sorted (a single rotation = one discontinuity), then write the four-way branch carefully and dry-run a case where the target is in the unsorted half.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan (Baseline)	`O(n)`	`O(1)`	Mention only to set the O(n) bar you're beating — then move on quickly, since the prompt demands O(log n).	Read
2	One-Pass Binary Search — Which Half Is Sorted (Optimal)Optimal	`O(log n)`	`O(1)`	The expected answer. Lead with 'one half around mid is always sorted' to show the key insight before coding.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewnums[mid] == target?nums[lo] <= nums[mid]? (left half sorted)YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan (Baseline)

TimeO(n)SpaceO(1)

Mention only to set the O(n) bar you're beating — then move on quickly, since the prompt demands O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the rotation entirely — what's the trivial way to find a value?

2Hint 2Explore hint

Scan every element and compare to the target.

3Hint 3Explore hint

It's O(n) and ignores both sortedness and rotation, so it's just a baseline.

A · Core idea

Walk the array and return the first index whose value equals the target, else -1.

Why mention it. It's a correctness anchor and a complexity to beat. Why it's wrong here. The prompt requires O(log n); a scan ignores the structure (sorted, single rotation) that lets us halve the search.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

i=0..3

4,5,6,7 — none equal 0

Statecontinue

Final result4

C · Code with teaching comments

Reference implementation previewpublic int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { return i; }Explore the full code

solution.javaJava

Linear Scan (Baseline) — reference

2 teaching notes

1
public int search(int[] nums, int target) {
2
    for (int i = 0; i < nums.length; i++) {
3
        // Ignores rotation and order entirely.
4
        if (nums[i] == target) {
5
            return i;
6
        }
7
    }
8
    // Target not present.
9
    return -1;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Rotation feels like it destroys sortedness, but it only introduces one discontinuity. A linear scan throws away that structure; binary search exploits it.

ComplexityO(n) time, O(1) space — Up to n comparisons, constant memory.

E · Edge cases and pitfalls2Submitting this when O(log n) is required.Explore edge cases

Pitfalls

Submitting this when O(log n) is required.
Assuming you must locate the pivot to do better — you don't.

03.2

Approach 2 of 2 · Optimal

One-Pass Binary Search — Which Half Is Sorted (Optimal)

TimeO(log n)SpaceO(1)

The expected answer. Lead with 'one half around mid is always sorted' to show the key insight before coding.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Picture cutting a sorted array once and swapping the pieces. Around any middle index, is it possible for BOTH halves to be broken at the same time?

2Hint 2Explore hint

Exactly one half [lo..mid] or [mid..hi] is a clean sorted run. Detect it by comparing nums[lo] with nums[mid].

3Hint 3Explore hint

If the sorted half's value range brackets the target, recurse into it; otherwise recurse into the other half. Keep the inclusive [lo, hi] template.

A · Core idea

Run a standard binary search, but augment the mid step to cope with rotation.

The structural fact. A single rotation of a sorted array creates exactly one point where a larger value is immediately followed by a smaller one. For any mid, the break point lies in at most one of the two halves [lo, mid] and [mid, hi] — so the other half is a contiguous sorted run. That guarantees that at every step at least one half is sorted, and we can reason about it precisely.

Detecting the sorted half. Compare nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half [lo, mid] is sorted (no break between them). Otherwise the break is on the left, which means the right half [mid, hi] is the sorted one. The <= matters: when lo == mid (window of size 1 or 2) the left half is trivially 'sorted', and <= keeps that case in the left branch.

Range-testing the target. Once we know which half is sorted, we know its exact value bounds, so we can ask in O(1) whether the target lies inside it. If the left half is sorted and nums[lo] <= target < nums[mid], the target — if present — must be in the left half, so set hi = mid - 1; otherwise it must be in the right half, so lo = mid + 1. Symmetrically, if the right half is sorted and nums[mid] < target <= nums[hi], search right (lo = mid + 1), else search left (hi = mid - 1).

Why the boundary comparisons use the asymmetric `<` / `<=`. We've already returned if nums[mid] == target, so mid itself is excluded. On the sorted left half the inclusive end is nums[lo] (could equal target) and the exclusive end is nums[mid] — hence nums[lo] <= target < nums[mid]. On the sorted right half it mirrors: nums[mid] < target <= nums[hi]. Getting these endpoints right is what separates a correct solution from one that drops targets sitting exactly at lo or hi.

Termination and absence. The window strictly shrinks every iteration (we always move past mid), so the loop ends; if it exits, the target isn't there and we return -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Array state

lo=0, hi=6

mid=3 (7). Left [4..7] sorted, 0 not inside → go right

lo ↓

[0]

[1]

[2]

mid ↓

[3]

[4]

[5]

hi ↓

[6]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

One-Pass Binary Search — Which Half Is Sorted (Optimal) — optimal

8 teaching notes

1
public int search(int[] nums, int target) {
2
    int lo = 0, hi = nums.length - 1;
3
    while (lo <= hi) {
4
        int mid = lo + (hi - lo) / 2;
5
        // Direct hit — return immediately so mid is excluded from later range tests.
6
        if (nums[mid] == target) {
7
            return mid;
8
        }
9
        if (nums[lo] <= nums[mid]) {            // left half sorted
10
            // Target lies within the sorted left half's value range → search left.
11
            if (nums[lo] <= target && target < nums[mid]) {
12
                // Discard mid and everything right of it.
13
                hi = mid - 1;
14
            // nums[lo] > nums[mid] → the break is on the left, so the RIGHT half is
15
            // sorted.
16
            } else {
17
                // Target not in the sorted left half → it can only be on the right.
18
                lo = mid + 1;
19
            }
20
        } else {                                // right half sorted
21
            // Target within the sorted right half's range → search right.
22
            if (nums[mid] < target && target <= nums[hi]) {
23
                lo = mid + 1;
24
            } else {
25
                hi = mid - 1;
26
            }
27
        }
28
    }
29
    // Window emptied → target absent.
30
    return -1;
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

You never need to know where the pivot is — only which side of mid is currently clean. That reframing (local sortedness, not global structure) is the reusable idea: it reappears in Find Minimum in Rotated Sorted Array and in the duplicates variant, where the only change is how you break the nums[lo] == nums[mid] tie.

ComplexityO(log n) time, O(1) space — Each iteration discards half the window with O(1) work, so O(log n) iterations and O(1) extra space.

E · Edge cases and pitfalls8nums = [1], target = 1 — lo=hi=0, mid=0, direct hit → return 0.Explore edge cases

Edge cases handled

nums = [1], target = 1lo=hi=0, mid=0, direct hit → return 0.
nums = [1], target = 0mid=0, no match, left half 'sorted', 0 not in [1,1) → lo=1, loop ends → -1.
nums = [3, 1], target = 1mid=0 (3). nums[lo]=3 <= 3 left sorted; 1 not in [3,3) → lo=1; then mid=1 → match, return 1.
un-rotated nums = [1,2,3,4,5], target = 4Left half always detected sorted → behaves exactly like plain binary search.

Pitfalls

Using `<` instead of `<=` in `nums[lo] <= nums[mid]` — mishandles the lo == mid window.
Wrong endpoint inclusivity in the range tests — drops targets equal to nums[lo] or nums[hi].
Trying to handle duplicates with this exact code — equal nums[lo]/nums[mid] is ambiguous and needs a separate shrink step.
Range-testing against the *unsorted* half, whose bounds don't bracket its contents.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Range-testing against the wrong (unsorted) half

You can only reason about value bounds on the SORTED half. Checking the target against the unsorted half's endpoints gives meaningless comparisons and wrong branches.

Explore the code comparison

Don't write this

# assumes left is always usable
if nums[lo] <= target <= nums[mid]:
    hi = mid - 1
else:
    lo = mid + 1

Write this instead

if nums[lo] <= nums[mid]:            # confirm left sorted first
    if nums[lo] <= target < nums[mid]:
        hi = mid - 1
    else:
        lo = mid + 1
else:
    if nums[mid] < target <= nums[hi]:
        lo = mid + 1
    else:
        hi = mid - 1

Strict vs non-strict boundary

mid is already excluded (we returned on equality), but lo and hi are not. Using `<` on the inclusive end drops a target equal to nums[lo] or nums[hi].

Explore the code comparison

Don't write this

if (nums[lo] < target && target < nums[mid]) {  // drops target == nums[lo]
    hi = mid - 1;
}

Write this instead

if (nums[lo] <= target && target < nums[mid]) {
    hi = mid - 1;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search + 'which half is sorted?'

Code pattern to memorize

while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target: return mid
    if nums[lo] <= nums[mid]:        # left half sorted
        if nums[lo] <= target < nums[mid]: hi = mid - 1
        else: lo = mid + 1
    else:                            # right half sorted
        if nums[mid] < target <= nums[hi]: lo = mid + 1
        else: hi = mid - 1
return -1

Rules to remember

1At every mid, compare nums[lo] to nums[mid] — if nums[lo] <= nums[mid] the left half is sorted, otherwise the right half is.
2Use <= in nums[lo] <= nums[mid] so the single-element case (lo == mid) is treated as a sorted left half.
3Only commit to a half after checking the target lies within that sorted half's value bounds; otherwise search the other half.
4Use the same overflow-safe mid = lo + (hi - lo) / 2 and inclusive while (lo <= hi) as plain binary search.
5You do not need to find the pivot first — one pass handles rotation directly.

Use this pattern when

A sorted array was rotated by an unknown amount and you need O(log n) lookup
Any 'piecewise sorted / one discontinuity' array where half is always clean
Follow-ups that combine rotation with search (find min, find pivot, search with duplicates)

Choose another pattern when

Array isn't rotated → plain binary search, no half-check needed
Duplicates are allowed (LeetCode 81) → `nums[lo] == nums[mid]` is ambiguous; shrink lo by one, worst case O(n)
You need the rotation count itself → that's Find Minimum, a simpler mid-vs-hi compare

Interview takeaway

The whole trick is that rotation creates exactly one 'break point', so one of the two halves around any mid is always a clean sorted range you can range-test against. Recognising 'at least one half is sorted' generalises to every rotated-array variant.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary search on a piecewise-sorted array. Recognise it when a sorted array is rotated/shifted once: at any mid, one half is a clean sorted run you can range-test. Same family as Find Minimum in Rotated Sorted Array and Find Peak Element.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Search in Rotated Sorted Array II
Coming soon
Duplicates allowed — when nums[lo] == nums[mid] == nums[hi], shrink both ends by one; worst case O(n).
Find Minimum in Rotated Sorted Array
Just locate the pivot by comparing nums[mid] to nums[hi] — no target needed.
Binary Search
The un-rotated base case — same template without the half-sorted branch.
Find Peak Element
Another 'compare mid to a neighbour to pick a half' binary search on an unsorted-but-structured array.

Same pattern

←

Binary Search

Continue · Next problem

Find Minimum in Rotated Sorted Array

mediumBinary SearchLC #33Asked very often

Search in Rotated Sorted Array

LCPractice

Binary Search · 2 of 16 · 10 min

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.

You must write an algorithm with O(log n) runtime complexity.

In plain English

Examples

Example 1

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Note: Rotated at pivot 4. 0 sits at index 4.

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Note: 3 is not present.

Example 3

Input: nums = [1], target = 0
Output: -1
Note: Single element, not the target.

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
All values of nums are unique
nums is an ascending array possibly rotated
-10⁴ ≤ target ≤ 10⁴

Clarifying questions4First question: Are the values guaranteed distinct?Explore questions

Q1.Are the values guaranteed distinct?
Yes here. Duplicates (LeetCode 81) break the `nums[lo] <= nums[mid]` test when they're equal and force a worst-case O(n) fallback.
Q2.Could the array be un-rotated (rotated by 0 or n)?
Yes — k can be 0, which means a normal sorted array. The same code handles it: the left half is always detected as sorted.
Q3.Do I need to find the pivot index first?
No. Finding the pivot then searching is a valid two-pass O(log n) approach, but the one-pass 'which half is sorted' method is cleaner and what interviewers look for.
Q4.What do I return when the target is absent?
-1, same as standard binary search.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can adapt the binary-search invariant to a non-monotonic array by reasoning about which half stays sorted, instead of giving up and scanning linearly.

Where candidates slip

Comparing only nums[mid] to target (plain binary search) and ignoring rotation, or getting the boundary `<=` wrong so a target equal to nums[lo] or nums[hi] is dropped.

How to stand out

Explain *why* one half is always sorted (a single rotation = one discontinuity), then write the four-way branch carefully and dry-run a case where the target is in the unsorted half.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan (Baseline)	`O(n)`	`O(1)`	Mention only to set the O(n) bar you're beating — then move on quickly, since the prompt demands O(log n).	Read
2	One-Pass Binary Search — Which Half Is Sorted (Optimal)Optimal	`O(log n)`	`O(1)`	The expected answer. Lead with 'one half around mid is always sorted' to show the key insight before coding.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan (Baseline)

TimeO(n)SpaceO(1)

Mention only to set the O(n) bar you're beating — then move on quickly, since the prompt demands O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Forget the rotation entirely — what's the trivial way to find a value?

2Hint 2Explore hint

Scan every element and compare to the target.

3Hint 3Explore hint

It's O(n) and ignores both sortedness and rotation, so it's just a baseline.

A · Core idea

Walk the array and return the first index whose value equals the target, else -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

i=0..3

4,5,6,7 — none equal 0

Statecontinue

Final result4

C · Code with teaching comments

Reference implementation previewpublic int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { return i; }Explore the full code

solution.javaJava

Linear Scan (Baseline) — reference

2 teaching notes

1
public int search(int[] nums, int target) {
2
    for (int i = 0; i < nums.length; i++) {
3
        // Ignores rotation and order entirely.
4
        if (nums[i] == target) {
5
            return i;
6
        }
7
    }
8
    // Target not present.
9
    return -1;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Rotation feels like it destroys sortedness, but it only introduces one discontinuity. A linear scan throws away that structure; binary search exploits it.

ComplexityO(n) time, O(1) space — Up to n comparisons, constant memory.

E · Edge cases and pitfalls2Submitting this when O(log n) is required.Explore edge cases

Pitfalls

Submitting this when O(log n) is required.
Assuming you must locate the pivot to do better — you don't.

03.2

Approach 2 of 2 · Optimal

One-Pass Binary Search — Which Half Is Sorted (Optimal)

TimeO(log n)SpaceO(1)

The expected answer. Lead with 'one half around mid is always sorted' to show the key insight before coding.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Picture cutting a sorted array once and swapping the pieces. Around any middle index, is it possible for BOTH halves to be broken at the same time?

2Hint 2Explore hint

Exactly one half [lo..mid] or [mid..hi] is a clean sorted run. Detect it by comparing nums[lo] with nums[mid].

3Hint 3Explore hint

If the sorted half's value range brackets the target, recurse into it; otherwise recurse into the other half. Keep the inclusive [lo, hi] template.

A · Core idea

Run a standard binary search, but augment the mid step to cope with rotation.

Termination and absence. The window strictly shrinks every iteration (we always move past mid), so the loop ends; if it exits, the target isn't there and we return -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Array state

lo=0, hi=6

mid=3 (7). Left [4..7] sorted, 0 not inside → go right

lo ↓

[0]

[1]

[2]

mid ↓

[3]

[4]

[5]

hi ↓

[6]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

One-Pass Binary Search — Which Half Is Sorted (Optimal) — optimal

8 teaching notes

1
public int search(int[] nums, int target) {
2
    int lo = 0, hi = nums.length - 1;
3
    while (lo <= hi) {
4
        int mid = lo + (hi - lo) / 2;
5
        // Direct hit — return immediately so mid is excluded from later range tests.
6
        if (nums[mid] == target) {
7
            return mid;
8
        }
9
        if (nums[lo] <= nums[mid]) {            // left half sorted
10
            // Target lies within the sorted left half's value range → search left.
11
            if (nums[lo] <= target && target < nums[mid]) {
12
                // Discard mid and everything right of it.
13
                hi = mid - 1;
14
            // nums[lo] > nums[mid] → the break is on the left, so the RIGHT half is
15
            // sorted.
16
            } else {
17
                // Target not in the sorted left half → it can only be on the right.
18
                lo = mid + 1;
19
            }
20
        } else {                                // right half sorted
21
            // Target within the sorted right half's range → search right.
22
            if (nums[mid] < target && target <= nums[hi]) {
23
                lo = mid + 1;
24
            } else {
25
                hi = mid - 1;
26
            }
27
        }
28
    }
29
    // Window emptied → target absent.
30
    return -1;
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(log n) time, O(1) space — Each iteration discards half the window with O(1) work, so O(log n) iterations and O(1) extra space.

E · Edge cases and pitfalls8nums = [1], target = 1 — lo=hi=0, mid=0, direct hit → return 0.Explore edge cases

Edge cases handled

nums = [1], target = 1lo=hi=0, mid=0, direct hit → return 0.
nums = [1], target = 0mid=0, no match, left half 'sorted', 0 not in [1,1) → lo=1, loop ends → -1.
nums = [3, 1], target = 1mid=0 (3). nums[lo]=3 <= 3 left sorted; 1 not in [3,3) → lo=1; then mid=1 → match, return 1.
un-rotated nums = [1,2,3,4,5], target = 4Left half always detected sorted → behaves exactly like plain binary search.

Pitfalls

Using `<` instead of `<=` in `nums[lo] <= nums[mid]` — mishandles the lo == mid window.
Wrong endpoint inclusivity in the range tests — drops targets equal to nums[lo] or nums[hi].
Trying to handle duplicates with this exact code — equal nums[lo]/nums[mid] is ambiguous and needs a separate shrink step.
Range-testing against the *unsorted* half, whose bounds don't bracket its contents.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Range-testing against the wrong (unsorted) half

You can only reason about value bounds on the SORTED half. Checking the target against the unsorted half's endpoints gives meaningless comparisons and wrong branches.

Explore the code comparison

Don't write this

# assumes left is always usable
if nums[lo] <= target <= nums[mid]:
    hi = mid - 1
else:
    lo = mid + 1

Write this instead

if nums[lo] <= nums[mid]:            # confirm left sorted first
    if nums[lo] <= target < nums[mid]:
        hi = mid - 1
    else:
        lo = mid + 1
else:
    if nums[mid] < target <= nums[hi]:
        lo = mid + 1
    else:
        hi = mid - 1

Strict vs non-strict boundary

mid is already excluded (we returned on equality), but lo and hi are not. Using `<` on the inclusive end drops a target equal to nums[lo] or nums[hi].

Explore the code comparison

Don't write this

if (nums[lo] < target && target < nums[mid]) {  // drops target == nums[lo]
    hi = mid - 1;
}

Write this instead

if (nums[lo] <= target && target < nums[mid]) {
    hi = mid - 1;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search + 'which half is sorted?'

Code pattern to memorize

while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target: return mid
    if nums[lo] <= nums[mid]:        # left half sorted
        if nums[lo] <= target < nums[mid]: hi = mid - 1
        else: lo = mid + 1
    else:                            # right half sorted
        if nums[mid] < target <= nums[hi]: lo = mid + 1
        else: hi = mid - 1
return -1

Rules to remember

1At every mid, compare nums[lo] to nums[mid] — if nums[lo] <= nums[mid] the left half is sorted, otherwise the right half is.
2Use <= in nums[lo] <= nums[mid] so the single-element case (lo == mid) is treated as a sorted left half.
3Only commit to a half after checking the target lies within that sorted half's value bounds; otherwise search the other half.
4Use the same overflow-safe mid = lo + (hi - lo) / 2 and inclusive while (lo <= hi) as plain binary search.
5You do not need to find the pivot first — one pass handles rotation directly.

Use this pattern when

A sorted array was rotated by an unknown amount and you need O(log n) lookup
Any 'piecewise sorted / one discontinuity' array where half is always clean
Follow-ups that combine rotation with search (find min, find pivot, search with duplicates)

Choose another pattern when

Array isn't rotated → plain binary search, no half-check needed
Duplicates are allowed (LeetCode 81) → `nums[lo] == nums[mid]` is ambiguous; shrink lo by one, worst case O(n)
You need the rotation count itself → that's Find Minimum, a simpler mid-vs-hi compare

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Search in Rotated Sorted Array II
Coming soon
Duplicates allowed — when nums[lo] == nums[mid] == nums[hi], shrink both ends by one; worst case O(n).
Find Minimum in Rotated Sorted Array
Just locate the pivot by comparing nums[mid] to nums[hi] — no target needed.
Binary Search
The un-rotated base case — same template without the half-sorted branch.
Find Peak Element
Another 'compare mid to a neighbour to pick a half' binary search on an unsorted-but-structured array.

Same pattern

←

Binary Search

Continue · Next problem

Find Minimum in Rotated Sorted Array