Loading…

easyBinary SearchLC #704Asked very often

Binary Search

Q: How do you solve Binary Search using the Linear Scan (Baseline) approach?

When to use it: Name it as the trivial O(n) baseline so the interviewer hears you frame the speed-up, then immediately pivot to binary search. Walk the array from index 0 and compare each element to `target`, returning the index on the first equal element and `-1` if the loop completes. **Why mention it.** It establishes a correct baseline and a complexity to beat. Stating 'the naive scan is O(n)' signals that you understand the cost you're about to improve on. **Why it's wrong for this problem.** The prompt explicitly demands `O(log n)`. A linear scan throws away the most valuable piece of information we were handed — that the array is sorted. Sortedness means one comparison can eliminate half the array, not just one element. Time complexity: O(n). Space complexity: O(1).

LCPractice

Binary Search · 1 of 16 · 8 min

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise, return -1.

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

In plain English

On a sorted array, comparing the target to the middle element tells you which half to keep. Each comparison throws away half the remaining candidates, so the worst case is log₂(n) comparisons. Return the index if found, else -1.

Examples

Example 1

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Note: 9 exists in nums and its index is 4.

Example 2

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Note: 2 does not exist in nums, so we return -1.

Example 3

Input: nums = [5], target = 5
Output: 0
Note: Single-element array; the `lo <= hi` condition is what lets us inspect index 0.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ < nums[i], target < 10⁴
All integers in nums are unique
nums is sorted in ascending order

Clarifying questions4First question: Is the array guaranteed sorted, and ascending or descending?Explore questions

Q1.Is the array guaranteed sorted, and ascending or descending?
Ascending here. Binary search needs a monotonic ordering; if it were descending you'd just flip the comparison.
Q2.Can there be duplicate values?
This problem guarantees uniqueness, so any matching index is fine. With duplicates you'd specify first or last occurrence and use a boundary-search variant.
Q3.What should I return if the target isn't present?
-1. A common follow-up (Search Insert Position) instead asks for the index where it *would* be inserted — that's `lo` after the loop.
Q4.How large can the array get — do I need to worry about overflow?
Here n ≤ 10⁴ so (lo + hi) won't overflow, but I'll write `lo + (hi - lo) / 2` anyway because it's the habit that matters on the variants with large bounds.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Search a sorted array for a target in O(log n). Maintain an inclusive window [lo, hi]; each step compute mid = lo + (hi - lo) / 2, compare nums[mid] to target, and discard the half that cannot contain it. The two things that break candidates are integer overflow on (lo + hi) and off-by-one bugs in the loop condition — use `while (lo <= hi)` with `hi = mid - 1` / `lo = mid + 1`.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can implement binary search bug-free under pressure — correct loop bounds, overflow-safe mid, and a termination guarantee — not just recite the idea.

Where candidates slip

Writing `mid = (lo + hi) / 2` (overflow), using `while (lo < hi)` with an inclusive window (skips the last element), or updating `lo = mid` instead of `mid + 1` (infinite loop).

How to stand out

State your invariant out loud ('the answer, if present, is always inside [lo, hi]'), justify the `<=`, and mention the overflow-safe mid formula before the interviewer has to ask.

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)`	Name it as the trivial O(n) baseline so the interviewer hears you frame the speed-up, then immediately pivot to binary search.	Read
2	Binary Search — Inclusive Bounds (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want. Describe the invariant ('answer stays inside [lo, hi]') as you write it.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind target in an arrayIs the array sorted?NoYesExplore 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)

Name it as the trivial O(n) baseline so the interviewer hears you frame the speed-up, then immediately pivot to binary search.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignoring the 'sorted' property, how would you find a value with no cleverness at all?

2Hint 2Explore hint

Walk every element left to right and compare it to the target.

3Hint 3Explore hint

Return the index on the first match, -1 if you reach the end. It works but it ignores the one fact (sortedness) that lets us go faster.

A · Core idea

Walk the array from index 0 and compare each element to target, returning the index on the first equal element and -1 if the loop completes.

Why mention it. It establishes a correct baseline and a complexity to beat. Stating 'the naive scan is O(n)' signals that you understand the cost you're about to improve on.

Why it's wrong for this problem. The prompt explicitly demands O(log n). A linear scan throws away the most valuable piece of information we were handed — that the array is sorted. Sortedness means one comparison can eliminate half the array, not just one element.

B · Visual dry run

Interactive dry run

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

nums = [-1, 0, 3, 5, 9, 12], target = 9

i=0

-1 == 9? no

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
        // One comparison per element — no use is made of the sorted order.
4
        if (nums[i] == target) {
5
            return i;
6
        }
7
    }
8
    // Fell off the end without a match.
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

The linear scan extracts exactly one bit of information per comparison ('is this the answer?'). Binary search extracts a far more valuable bit ('is the answer left or right of here?'), which is why it collapses n into log n.

ComplexityO(n) time, O(1) space — One pass over up to n elements, a single comparison each, no extra memory.

E · Edge cases and pitfalls2Submitting this when the prompt demands O(log n) — it passes small tests but signals you missed the point.Explore edge cases

Pitfalls

Submitting this when the prompt demands O(log n) — it passes small tests but signals you missed the point.
Forgetting the trailing return -1 when no element matches.

03.2

Approach 2 of 2 · Optimal

Binary Search — Inclusive Bounds (Optimal)

TimeO(log n)SpaceO(1)

The answer they want. Describe the invariant ('answer stays inside [lo, hi]') as you write it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array is sorted. If you look at the middle element and it's smaller than the target, what does that tell you about everything to its left?

2Hint 2Explore hint

Keep a window [lo, hi]. Look at mid; if nums[mid] < target the answer must be to the right, so move lo past mid; if it's larger, move hi before mid.

3Hint 3Explore hint

Loop while lo <= hi. Compute mid as lo + (hi - lo) / 2 to avoid overflow, and always set lo = mid + 1 or hi = mid - 1 so the window strictly shrinks.

A · Core idea

Maintain an inclusive window [lo, hi] that always contains the answer if it exists. Initialise lo = 0, hi = n - 1. While lo <= hi, look at mid = lo + (hi - lo) / 2. If nums[mid] == target, return mid. If nums[mid] < target, the target (being larger) must lie strictly to the right, so set lo = mid + 1. Otherwise it lies strictly to the left, so set hi = mid - 1. If the loop exits, the window is empty and the target is absent — return -1.

The invariant that makes it correct. At every step, if the target is in the array, it is somewhere in [lo, hi]. Each comparison lets us discard the half that provably cannot contain it: because the array is sorted, nums[mid] < target means every index ≤ mid is also < target, so none of them can be the answer. Discarding half each time gives the logarithmic bound.

Why `lo <= hi` and not `lo < hi`. With inclusive bounds, the window [lo, hi] is non-empty exactly when lo <= hi. When lo == hi there is still one element left to check — the target could be it. Using < would skip that final element and miss answers (e.g. a single-element array, or the target sitting at the last position the search narrows to).

Why `mid = lo + (hi - lo) / 2` instead of `(lo + hi) / 2`. Both compute the same midpoint mathematically, but lo + hi can exceed Integer.MAX_VALUE in Java when both indices are large, wrapping to a negative number and throwing ArrayIndexOutOfBoundsException. lo + (hi - lo) / 2 never forms the large intermediate sum, so it's overflow-safe. It's a free habit that prevents a notorious bug — famously latent in the JDK's own binarySearch for nearly a decade.

Why `mid + 1` / `mid - 1` and not `mid`. We've already tested mid and it wasn't the answer, so excluding it is correct and guarantees the window shrinks by at least one every iteration. Setting lo = mid when lo == mid would leave the window unchanged and loop forever.

B · Visual dry run

Interactive dry run

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

nums = [-1, 0, 3, 5, 9, 12], target = 9

Array state

lo=0, hi=5

mid=2, nums[2]=3 < 9 → discard left half

lo ↓

-1

[0]

[1]

mid ↓

[2]

[3]

[4]

hi ↓

[5]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Binary Search — Inclusive Bounds (Optimal) — optimal

7 teaching notes

1
public int search(int[] nums, int target) {
2
    // Inclusive window: hi is the LAST valid index, not length.
3
    int lo = 0, hi = nums.length - 1;
4
    // The `=` keeps a one-element window alive so we still check it.
5
    while (lo <= hi) {
6
        // Overflow-safe midpoint — never forms the large sum lo + hi.
7
        int mid = lo + (hi - lo) / 2;
8
        if (nums[mid] == target) {
9
            return mid;
10
        // Target is bigger, so everything ≤ mid is too small → discard the left half.
11
        } else if (nums[mid] < target) {
12
            // Move PAST mid (already tested) so the window strictly shrinks.
13
            lo = mid + 1;
14
        } else {
15
            // Symmetric: target smaller → discard the right half including mid.
16
            hi = mid - 1;
17
        }
18
    }
19
    // Window empty (lo > hi) → target absent.
20
    return -1;
21
}

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

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

Binary search is less about arrays and more about predicates: you're locating the boundary of a monotone condition. Once you internalise the inclusive-bounds template (while lo <= hi, move past mid, return -1/lo at the end), every variant — rotated arrays, 2D matrices, 'smallest speed that works' — is the same skeleton with a different comparison in the middle.

ComplexityO(log n) time, O(1) space — Each iteration halves the window size, so the number of iterations is ⌈log₂(n+1)⌉ = O(log n). Only a few scalar variables are used → O(1) space.

E · Edge cases and pitfalls8nums = [5], target = 5 — lo=hi=0, mid=0, nums[0]==5 → return 0. The `<=` is what lets the single-element window be checked.Explore edge cases

Edge cases handled

nums = [5], target = 5lo=hi=0, mid=0, nums[0]==5 → return 0. The `<=` is what lets the single-element window be checked.
nums = [5], target = 2mid=0, 5 > 2 → hi=-1, loop ends, return -1.
nums = [2, 5], target = 5lo=0,hi=1,mid=0 → 2<5 → lo=1; then lo=hi=1,mid=1 → match, return 1.
target smaller than all / larger than allWindow collapses to one side and exits with lo>hi → return -1, no out-of-bounds access.

Pitfalls

Using `mid = (lo + hi) / 2` — overflows int in Java for large indices.
Using `while (lo < hi)` with inclusive bounds — skips the last element.
Updating `lo = mid` / `hi = mid` — can spin forever when lo == mid.
Returning `lo` thinking it's the index when not found (that's the insertion point, not a match).

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.

Overflow in the midpoint

In Java, `lo + hi` is computed as a 32-bit int. For large arrays lo + hi can exceed 2^31 − 1, wrap negative, and crash with ArrayIndexOutOfBoundsException. This bug lived in the JDK for years.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2;

Write this instead

int mid = lo + (hi - lo) / 2;

Wrong loop condition for inclusive bounds

With hi = nums.length - 1 (inclusive), the window is non-empty when lo == hi. Using `<` exits one step early and misses a target sitting at that last position.

Explore the code comparison

Don't write this

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

Write this instead

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

Not moving past mid (infinite loop)

When lo == hi == mid, setting lo = mid leaves the window unchanged, so the while loop never terminates.

Explore the code comparison

Don't write this

if nums[mid] < target:
    lo = mid
else:
    hi = mid

Write this instead

if nums[mid] < target:
    lo = mid + 1
else:
    hi = mid - 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Halve the search space on sorted data

Code pattern to memorize

lo, hi = 0, n - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target: return mid
    elif nums[mid] < target: lo = mid + 1
    else: hi = mid - 1
return -1

Rules to remember

1Use mid = lo + (hi - lo) / 2, never (lo + hi) / 2 — the latter overflows int in Java when lo + hi > 2^31 − 1.
2With an inclusive [lo, hi] window, the loop is while (lo <= hi) — the = is required so a single-element window is still inspected.
3Always move past mid: lo = mid + 1 or hi = mid - 1. Setting lo = mid or hi = mid can loop forever.
4Return -1 (or the insertion point) after the loop — falling off the end means the target is absent.
5Pick one convention (inclusive [lo, hi]) and use it everywhere; mixing inclusive and exclusive bounds is the #1 source of binary-search bugs.

Use this pattern when

Array (or answer space) is **sorted / monotonic** and you need a value or boundary
Lookups must be faster than O(n) — repeated queries on static sorted data
Finding a threshold: first/last index satisfying a predicate
The phrase 'minimize/maximize X such that a feasibility check passes' → binary search on the answer

Choose another pattern when

Data is unsorted and you only search once → a linear scan or hash set is simpler and O(n)
Data changes between queries and you'd have to re-sort each time → consider a balanced BST / heap
You need *all* matches, not a single index → linear scan or expand around the found index

Interview takeaway

Binary search is the canonical 'halve the search space' move. Master the inclusive-bounds template once and you can retarget it to rotated arrays, 2D matrices, and 'binary search on the answer' problems like Koko Eating Bananas — same skeleton, different comparison.

Continue

Transfer the pattern to another problem

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

Transferable patternThe canonical Binary Search template. Recognise it whenever data is sorted or a predicate is monotonic and you can discard half the search space per comparison. The exact skeleton powers Search in Rotated Sorted Array, Search a 2D Matrix, Find Minimum in Rotated Sorted Array, and 'binary search on the answer' problems like Koko Eating Bananas.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Search Insert Position
Same template, but return `lo` after the loop — that's where the target would be inserted.
Search in Rotated Sorted Array
Array is rotated — decide which half is sorted, then binary search the half that could contain the target.
Koko Eating Bananas
Binary search on the *answer* (eating speed) rather than on array indices.
Find First and Last Position
Coming soon
Two boundary searches — one biased left, one biased right — to handle duplicates.

Same pattern

Continue · Next problem

Search in Rotated Sorted Array

easyBinary SearchLC #704Asked very often

Binary Search

LCPractice

Binary Search · 1 of 16 · 8 min

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

In plain English

Examples

Example 1

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Note: 9 exists in nums and its index is 4.

Example 2

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Note: 2 does not exist in nums, so we return -1.

Example 3

Input: nums = [5], target = 5
Output: 0
Note: Single-element array; the `lo <= hi` condition is what lets us inspect index 0.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ < nums[i], target < 10⁴
All integers in nums are unique
nums is sorted in ascending order

Clarifying questions4First question: Is the array guaranteed sorted, and ascending or descending?Explore questions

Q1.Is the array guaranteed sorted, and ascending or descending?
Ascending here. Binary search needs a monotonic ordering; if it were descending you'd just flip the comparison.
Q2.Can there be duplicate values?
This problem guarantees uniqueness, so any matching index is fine. With duplicates you'd specify first or last occurrence and use a boundary-search variant.
Q3.What should I return if the target isn't present?
-1. A common follow-up (Search Insert Position) instead asks for the index where it *would* be inserted — that's `lo` after the loop.
Q4.How large can the array get — do I need to worry about overflow?
Here n ≤ 10⁴ so (lo + hi) won't overflow, but I'll write `lo + (hi - lo) / 2` anyway because it's the habit that matters on the variants with large bounds.

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 implement binary search bug-free under pressure — correct loop bounds, overflow-safe mid, and a termination guarantee — not just recite the idea.

Where candidates slip

Writing `mid = (lo + hi) / 2` (overflow), using `while (lo < hi)` with an inclusive window (skips the last element), or updating `lo = mid` instead of `mid + 1` (infinite loop).

How to stand out

State your invariant out loud ('the answer, if present, is always inside [lo, hi]'), justify the `<=`, and mention the overflow-safe mid formula before the interviewer has to ask.

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)`	Name it as the trivial O(n) baseline so the interviewer hears you frame the speed-up, then immediately pivot to binary search.	Read
2	Binary Search — Inclusive Bounds (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want. Describe the invariant ('answer stays inside [lo, hi]') as you write it.	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)

Name it as the trivial O(n) baseline so the interviewer hears you frame the speed-up, then immediately pivot to binary search.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignoring the 'sorted' property, how would you find a value with no cleverness at all?

2Hint 2Explore hint

Walk every element left to right and compare it to the target.

3Hint 3Explore hint

Return the index on the first match, -1 if you reach the end. It works but it ignores the one fact (sortedness) that lets us go faster.

A · Core idea

Walk the array from index 0 and compare each element to target, returning the index on the first equal element and -1 if the loop completes.

Why mention it. It establishes a correct baseline and a complexity to beat. Stating 'the naive scan is O(n)' signals that you understand the cost you're about to improve on.

B · Visual dry run

Interactive dry run

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

nums = [-1, 0, 3, 5, 9, 12], target = 9

i=0

-1 == 9? no

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
        // One comparison per element — no use is made of the sorted order.
4
        if (nums[i] == target) {
5
            return i;
6
        }
7
    }
8
    // Fell off the end without a match.
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

ComplexityO(n) time, O(1) space — One pass over up to n elements, a single comparison each, no extra memory.

E · Edge cases and pitfalls2Submitting this when the prompt demands O(log n) — it passes small tests but signals you missed the point.Explore edge cases

Pitfalls

Submitting this when the prompt demands O(log n) — it passes small tests but signals you missed the point.
Forgetting the trailing return -1 when no element matches.

03.2

Approach 2 of 2 · Optimal

Binary Search — Inclusive Bounds (Optimal)

TimeO(log n)SpaceO(1)

The answer they want. Describe the invariant ('answer stays inside [lo, hi]') as you write it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array is sorted. If you look at the middle element and it's smaller than the target, what does that tell you about everything to its left?

2Hint 2Explore hint

Keep a window [lo, hi]. Look at mid; if nums[mid] < target the answer must be to the right, so move lo past mid; if it's larger, move hi before mid.

3Hint 3Explore hint

Loop while lo <= hi. Compute mid as lo + (hi - lo) / 2 to avoid overflow, and always set lo = mid + 1 or hi = mid - 1 so the window strictly shrinks.

A · Core idea

B · Visual dry run

Interactive dry run

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

nums = [-1, 0, 3, 5, 9, 12], target = 9

Array state

lo=0, hi=5

mid=2, nums[2]=3 < 9 → discard left half

lo ↓

-1

[0]

[1]

mid ↓

[2]

[3]

[4]

hi ↓

[5]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Binary Search — Inclusive Bounds (Optimal) — optimal

7 teaching notes

1
public int search(int[] nums, int target) {
2
    // Inclusive window: hi is the LAST valid index, not length.
3
    int lo = 0, hi = nums.length - 1;
4
    // The `=` keeps a one-element window alive so we still check it.
5
    while (lo <= hi) {
6
        // Overflow-safe midpoint — never forms the large sum lo + hi.
7
        int mid = lo + (hi - lo) / 2;
8
        if (nums[mid] == target) {
9
            return mid;
10
        // Target is bigger, so everything ≤ mid is too small → discard the left half.
11
        } else if (nums[mid] < target) {
12
            // Move PAST mid (already tested) so the window strictly shrinks.
13
            lo = mid + 1;
14
        } else {
15
            // Symmetric: target smaller → discard the right half including mid.
16
            hi = mid - 1;
17
        }
18
    }
19
    // Window empty (lo > hi) → target absent.
20
    return -1;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 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 halves the window size, so the number of iterations is ⌈log₂(n+1)⌉ = O(log n). Only a few scalar variables are used → O(1) space.

E · Edge cases and pitfalls8nums = [5], target = 5 — lo=hi=0, mid=0, nums[0]==5 → return 0. The `<=` is what lets the single-element window be checked.Explore edge cases

Edge cases handled

nums = [5], target = 5lo=hi=0, mid=0, nums[0]==5 → return 0. The `<=` is what lets the single-element window be checked.
nums = [5], target = 2mid=0, 5 > 2 → hi=-1, loop ends, return -1.
nums = [2, 5], target = 5lo=0,hi=1,mid=0 → 2<5 → lo=1; then lo=hi=1,mid=1 → match, return 1.
target smaller than all / larger than allWindow collapses to one side and exits with lo>hi → return -1, no out-of-bounds access.

Pitfalls

Using `mid = (lo + hi) / 2` — overflows int in Java for large indices.
Using `while (lo < hi)` with inclusive bounds — skips the last element.
Updating `lo = mid` / `hi = mid` — can spin forever when lo == mid.
Returning `lo` thinking it's the index when not found (that's the insertion point, not a match).

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.

Overflow in the midpoint

In Java, `lo + hi` is computed as a 32-bit int. For large arrays lo + hi can exceed 2^31 − 1, wrap negative, and crash with ArrayIndexOutOfBoundsException. This bug lived in the JDK for years.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2;

Write this instead

int mid = lo + (hi - lo) / 2;

Wrong loop condition for inclusive bounds

With hi = nums.length - 1 (inclusive), the window is non-empty when lo == hi. Using `<` exits one step early and misses a target sitting at that last position.

Explore the code comparison

Don't write this

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

Write this instead

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

Not moving past mid (infinite loop)

When lo == hi == mid, setting lo = mid leaves the window unchanged, so the while loop never terminates.

Explore the code comparison

Don't write this

if nums[mid] < target:
    lo = mid
else:
    hi = mid

Write this instead

if nums[mid] < target:
    lo = mid + 1
else:
    hi = mid - 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Halve the search space on sorted data

Code pattern to memorize

lo, hi = 0, n - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target: return mid
    elif nums[mid] < target: lo = mid + 1
    else: hi = mid - 1
return -1

Rules to remember

1Use mid = lo + (hi - lo) / 2, never (lo + hi) / 2 — the latter overflows int in Java when lo + hi > 2^31 − 1.
2With an inclusive [lo, hi] window, the loop is while (lo <= hi) — the = is required so a single-element window is still inspected.
3Always move past mid: lo = mid + 1 or hi = mid - 1. Setting lo = mid or hi = mid can loop forever.
4Return -1 (or the insertion point) after the loop — falling off the end means the target is absent.
5Pick one convention (inclusive [lo, hi]) and use it everywhere; mixing inclusive and exclusive bounds is the #1 source of binary-search bugs.

Use this pattern when

Array (or answer space) is **sorted / monotonic** and you need a value or boundary
Lookups must be faster than O(n) — repeated queries on static sorted data
Finding a threshold: first/last index satisfying a predicate
The phrase 'minimize/maximize X such that a feasibility check passes' → binary search on the answer

Choose another pattern when

Data is unsorted and you only search once → a linear scan or hash set is simpler and O(n)
Data changes between queries and you'd have to re-sort each time → consider a balanced BST / heap
You need *all* matches, not a single index → linear scan or expand around the found index

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 Insert Position
Same template, but return `lo` after the loop — that's where the target would be inserted.
Search in Rotated Sorted Array
Array is rotated — decide which half is sorted, then binary search the half that could contain the target.
Koko Eating Bananas
Binary search on the *answer* (eating speed) rather than on array indices.
Find First and Last Position
Coming soon
Two boundary searches — one biased left, one biased right — to handle duplicates.

Same pattern

Continue · Next problem

Search in Rotated Sorted Array