Loading…

easyBinary SearchLC #35Frequently asked

Search Insert Position

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

When to use it: Name it as the trivial O(n) baseline to frame the speed-up, then immediately pivot to binary search since the prompt demands O(log n). Walk the array from the front and return the first index `i` where `nums[i] >= target`. If you reach the end without finding one, return `n` because the target is larger than everything. **Why this is correct.** The insertion point is, by definition, the first position whose element is *not less than* the target — that's where the target slots in to preserve sorted order. Whether the target is present (`nums[i] == target`) or absent (`nums[i] > target`), the *first* index satisfying `nums[i] >= target` is the right answer in both cases, which is why a single condition handles found and not-found together. **Why we don't ship it.** The prompt explicitly demands `O(log n)`. A linear scan throws away the one fact we were handed — sortedness — that lets a single comparison eliminate half the array instead of one element. For `n = 10⁴` it passes, but it tells the interviewer you didn't use the structure of the input. **What it teaches.** Framing the scan around the predicate `nums[i] >= target` (rather than `nums[i] == target`) is exactly the mental model binary search will accelerate: we're locating the *boundary* of a monotone condition, not hunting for one specific value. Time complexity: O(n). Space complexity: O(1).

LCPractice

Binary Search · 9 of 16 · 9 min

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

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

In plain English

We want the position of `target` if present, otherwise the position it should occupy to keep `nums` sorted. That position equals the number of elements strictly less than `target`. Because the array is sorted, that count is exactly the left boundary a binary search converges to — so the found and not-found cases share one answer.

Examples

Example 1

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Note: 5 is present at index 2.

Example 2

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Note: 2 is absent; it would sit between 1 and 3, i.e. index 1.

Example 3

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Note: 7 is larger than everything, so it appends at index 4 (the length).

Example 4

Input: nums = [1, 3, 5, 6], target = 0
Output: 0
Note: 0 is smaller than everything, so it goes at the front, index 0.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums contains distinct values sorted in ascending order
-10⁴ ≤ target ≤ 10⁴

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

Q1.Are the values guaranteed distinct and sorted ascending?
Yes on both. Distinctness means I don't have to worry about which duplicate to land on; sorted ascending is what lets binary search apply.
Q2.If the target is larger than every element, what do I return?
`n` (the length) — it gets appended at the end. The lower-bound search returns exactly that because `lo` walks past the last index.
Q3.If the target is smaller than every element?
`0` — it goes at the front. `lo` never advances, so the loop leaves it at 0.
Q4.Does the problem really need O(log n), or would a scan pass?
A linear scan passes the tests for n ≤ 10⁴, but the prompt explicitly asks for O(log n). I'll mention the scan as a baseline and implement binary search.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find a target in a sorted array of distinct integers, or the index where it would be inserted to keep the array sorted. This is the canonical lower-bound binary search: maintain an inclusive window [lo, hi], move past mid each step, and the key trick is that after the loop `lo` is exactly the insertion point — return it whether or not the target was found. No special-casing the 'not found' branch.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand what the binary-search pointers *mean* after the loop — not just how to find an exact hit. Returning `lo` for the not-found case without an extra scan is the signal that you grasp the invariant rather than memorising the template.

Where candidates slip

Falling back to a linear scan to find the insertion point after binary search 'fails', or returning `-1`/`hi`/`mid` instead of `lo` — off-by-one at the boundary.

How to stand out

Say out loud: 'when the loop ends, `lo` is the number of elements strictly less than target, which is exactly the insertion index'. Then note it unifies the found and not-found cases into one return statement.

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 to frame the speed-up, then immediately pivot to binary search since the prompt demands O(log n).	Read
2	Lower-Bound Binary Search (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want. Describe the invariant ('answer stays in [lo, hi]') and the punchline ('lo is the insertion point after the loop') as you write it.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewWhere does target go in a sorted 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 to frame the speed-up, then immediately pivot to binary search since the prompt demands O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignore the sortedness for a moment — walk left to right. What's the first index where the array element is no longer smaller than the target?

2Hint 2Explore hint

The insertion point is the first index `i` with `nums[i] >= target`. Scan until you find it.

3Hint 3Explore hint

If you never find such an index, every element was smaller, so the answer is `n` (append at the end).

A · Core idea

Walk the array from the front and return the first index i where nums[i] >= target. If you reach the end without finding one, return n because the target is larger than everything.

Why this is correct. The insertion point is, by definition, the first position whose element is not less than the target — that's where the target slots in to preserve sorted order. Whether the target is present (nums[i] == target) or absent (nums[i] > target), the first index satisfying nums[i] >= target is the right answer in both cases, which is why a single condition handles found and not-found together.

Why we don't ship it. The prompt explicitly demands O(log n). A linear scan throws away the one fact we were handed — sortedness — that lets a single comparison eliminate half the array instead of one element. For n = 10⁴ it passes, but it tells the interviewer you didn't use the structure of the input.

What it teaches. Framing the scan around the predicate nums[i] >= target (rather than nums[i] == target) is exactly the mental model binary search will accelerate: we're locating the boundary of a monotone condition, not hunting for one specific value.

B · Visual dry run

Interactive dry run

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

nums = [1, 3, 5, 6], target = 2

i=0

nums[0]=1 >= 2? no

Statecontinue

Final result1

C · Code with teaching comments

Reference implementation previewpublic int searchInsert(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 searchInsert(int[] nums, int target) {
2
    for (int i = 0; i < nums.length; i++) {
3
        // First element NOT smaller than target — handles found (==) and not-found (>)
4
        // in one test.
5
        if (nums[i] >= target) {
6
            return i;
7
        }
8
    }
9
    // Fell off the end → target exceeds everything → append at index n.
10
    return nums.length;
11
}

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

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

The scan extracts one bit per comparison ('is this the boundary?'). Binary search extracts a stronger bit ('is the boundary left or right of here?'), collapsing n into log n. Reframing the goal as 'first index with nums[i] >= target' is what makes the jump to binary search natural.

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

E · Edge cases and pitfalls3Comparing with `==` only — you'll miss the insertion point entirely when the target is absent.Explore edge cases

Pitfalls

Comparing with `==` only — you'll miss the insertion point entirely when the target is absent.
Forgetting the trailing `return n` for the 'larger than everything' case.
Submitting this when the prompt demands O(log n) — it passes but signals you ignored sortedness.

03.2

Approach 2 of 2 · Optimal

Lower-Bound Binary Search (Optimal)

TimeO(log n)SpaceO(1)

The answer they want. Describe the invariant ('answer stays in [lo, hi]') and the punchline ('lo is the insertion point after the loop') as you write it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array is sorted, so you can binary search. The twist: the target might be absent, but you still owe an index. Where do the pointers end up when the search 'fails'?

2Hint 2Explore hint

Run the standard inclusive-bounds search. If `nums[mid] == target` return `mid`. Otherwise narrow the window exactly as in plain binary search.

3Hint 3Explore hint

When the loop exits, `lo` has crossed past every element smaller than the target — that count is precisely the insertion index. Return `lo`, no special case.

A · Core idea

Maintain an inclusive window [lo, hi] with lo = 0, hi = n - 1. While lo <= hi, compute mid = lo + (hi - lo) / 2. If nums[mid] == target, return mid. If nums[mid] < target, the boundary is strictly to the right, so set lo = mid + 1. Otherwise it is at mid or to the left, so set hi = mid - 1. When the loop ends, return `lo`.

The invariant, stated precisely. Throughout the loop, every index < lo holds a value strictly less than target, and every index > hi holds a value greater than or equal to target. The window [lo, hi] is the still-undecided middle. Each comparison shifts one boundary inward: a nums[mid] < target proves indices 0..mid are all below target (sortedness), so lo jumps to mid + 1; a nums[mid] > target proves mid..n-1 are all at-or-above target, so hi drops to mid - 1.

Why `lo` is the answer when the loop exits. The loop stops when lo > hi, meaning the undecided window is empty. At that instant, the invariant says everything left of lo is < target and everything from lo onward is >= target. The insertion point is by definition the first index whose value is not less than the target — that is exactly lo. So the same lo is correct whether the target would land among existing elements, at the very front (lo stays 0), or past the end (lo becomes n). One return statement covers all three.

Why we still check `==` and return `mid` early. When the target is present we can return its index the moment we land on it — a small optimisation. But note we don't strictly need it: if you delete the equality branch and only keep < / >=, the loop still converges with lo pointing at the existing target's index. Many interviewers like the pure lower-bound form for that reason; the explicit == is just an early exit.

Why `mid = lo + (hi - lo) / 2` and `while (lo <= hi)`. Same discipline as plain binary search: lo + (hi - lo) / 2 never forms the overflow-prone sum lo + hi, and the inclusive <= keeps the final one-element window alive so a target sitting at that last spot isn't skipped. Moving past mid every step (mid + 1 / mid - 1) guarantees the window strictly shrinks and the loop terminates.

B · Visual dry run

Interactive dry run

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

nums = [1, 3, 5, 6], target = 2

Array state

lo=0, hi=3

mid=1, nums[1]=3 > 2 → discard right half

lo ↓

[0]

mid ↓

[1]

[2]

hi ↓

[3]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Lower-Bound Binary Search (Optimal) — optimal

6 teaching notes

1
public int searchInsert(int[] nums, int target) {
2
    // Inclusive window; hi is the LAST valid index.
3
    int lo = 0, hi = nums.length - 1;
4
    // The `=` keeps a one-element window alive so the last candidate is inspected.
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
        // Everything ≤ mid is too small → boundary is to the right → lo = mid + 1.
11
        } else if (nums[mid] < target) {
12
            lo = mid + 1;
13
        } else {
14
            // nums[mid] >= target → mid could be the boundary, but search left for an
15
            // earlier one.
16
            hi = mid - 1;
17
        }
18
    }
19
    // Loop exits with lo = count of elements < target = the insertion point. No special
20
    // case.
21
    return lo;
22
}

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

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

The whole problem is one realisation: a binary search doesn't just answer 'is it here?' — when it ends, lo is the count of elements strictly less than the target, i.e. the lower_bound. Internalise that and 'insertion point', 'ceil index', 'first index >= x', and 'how many are below the threshold' all become the same three lines with return lo at the bottom.

ComplexityO(log n) time, O(1) space — Each iteration halves the window `[lo, hi]`, so it runs in ⌈log₂(n+1)⌉ = O(log n) steps. Only scalar variables are used → O(1) space.

E · Edge cases and pitfalls8nums = [1, 3, 5, 6], target = 7 — Every element < 7, so lo keeps advancing until lo = 4 = n. Returns 4 (append at end).Explore edge cases

Edge cases handled

nums = [1, 3, 5, 6], target = 7Every element < 7, so lo keeps advancing until lo = 4 = n. Returns 4 (append at end).
nums = [1, 3, 5, 6], target = 0nums[mid] > 0 always, so hi keeps shrinking and lo never moves. Returns 0 (front).
nums = [1], target = 1mid=0, nums[0]==1 → return 0 immediately.
nums = [1], target = 0mid=0, 1 > 0 → hi=-1, loop ends, return lo=0.

Pitfalls

Returning `-1` for the not-found case — this problem wants an index, never -1.
Returning `hi` or `mid` instead of `lo` — `hi` is `lo - 1` after the loop, off by one.
Doing a linear scan after binary search 'fails' — defeats the O(log n) requirement.
Using `mid = (lo + hi) / 2` (overflow) or `while (lo < hi)` with inclusive bounds (skips the last element).

Practice

Try the solution yourself

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

Editable code previewpublic int searchInsert(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.

Returning the wrong pointer after the loop

When the loop exits, `hi` equals `lo - 1`. Returning `hi` gives an index one too small; only `lo` equals the count of elements below target (the insertion point).

Explore the code comparison

Don't write this

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

Write this instead

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

Returning -1 for a missing target

This is a copy of plain binary search where -1 means 'absent'. But Search Insert Position must return an index in every case — the insertion point, which is `lo`.

Explore the code comparison

Don't write this

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

Write this instead

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 lo

Overflow in the midpoint

In Java `lo + hi` is a 32-bit int; for large arrays it can exceed 2^31 − 1, wrap negative, and crash with ArrayIndexOutOfBoundsException. Use the difference form.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2;

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Lower-bound binary search — first index with nums[i] >= target

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 lo   # insertion point, no special case

Rules to remember

1After an inclusive-bounds loop exits, `lo` is the insertion point — the count of elements strictly less than target. Return it directly.
2Use mid = lo + (hi - lo) / 2, never (lo + hi) / 2 — the latter overflows int in Java for large indices.
3Loop with while (lo <= hi) and inclusive hi = n - 1; the = keeps the final one-element window alive.
4Always move past mid (lo = mid + 1 / hi = mid - 1) so the window strictly shrinks and the loop terminates.
5Returning lo (not hi or mid) is what makes this work — hi after the loop is lo - 1, one short.

Use this pattern when

Sorted array + 'where does X go?' / 'first index >= X' / 'insertion point'
You need a boundary, not just an exact match — the target may be absent
Counting elements less than a threshold in O(log n)
Any 'lower_bound' / 'ceil index' phrasing on monotonic data

Choose another pattern when

Array is unsorted → sort first (O(n log n)) or just scan, binary search needs order
You only ever need exact presence, never the position → a hash set is simpler
Duplicates with a 'first/last occurrence' twist → that's the boundary-search variant (LC 34), slightly different

Interview takeaway

Search Insert Position is binary search's gateway to *boundary* search: the answer isn't 'is it here?' but 'where is the dividing line?'. The single insight — that `lo` after the loop counts how many elements are below target — generalises to every lower_bound/upper_bound problem you'll ever see.

Continue

Transfer the pattern to another problem

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

Transferable patternThe lower-bound (a.k.a. ceil-index / insertion-point) flavour of binary search. Recognise it whenever a sorted array or monotone predicate asks 'where does X go?' or 'first index satisfying the condition?'. The defining move is returning `lo` after the loop; the same skeleton powers Find First and Last Position, First Bad Version, and counting-below-threshold queries.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Search
The base template — return -1 when absent instead of the insertion point.
Find First and Last Position of Element in Sorted Array
Coming soon
Two boundary searches (lower_bound and upper_bound) to handle duplicates.
First Bad Version
Coming soon
Lower-bound search on a monotone predicate instead of array values.
Search in Rotated Sorted Array
Decide which half is sorted first, then binary search that half.

Same pattern

←

Find Peak Element

Continue · Next problem

Aggressive Cows

easyBinary SearchLC #35Frequently asked

Search Insert Position

LCPractice

Binary Search · 9 of 16 · 9 min

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

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

In plain English

Examples

Example 1

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Note: 5 is present at index 2.

Example 2

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Note: 2 is absent; it would sit between 1 and 3, i.e. index 1.

Example 3

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Note: 7 is larger than everything, so it appends at index 4 (the length).

Example 4

Input: nums = [1, 3, 5, 6], target = 0
Output: 0
Note: 0 is smaller than everything, so it goes at the front, index 0.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums contains distinct values sorted in ascending order
-10⁴ ≤ target ≤ 10⁴

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

Q1.Are the values guaranteed distinct and sorted ascending?
Yes on both. Distinctness means I don't have to worry about which duplicate to land on; sorted ascending is what lets binary search apply.
Q2.If the target is larger than every element, what do I return?
`n` (the length) — it gets appended at the end. The lower-bound search returns exactly that because `lo` walks past the last index.
Q3.If the target is smaller than every element?
`0` — it goes at the front. `lo` never advances, so the loop leaves it at 0.
Q4.Does the problem really need O(log n), or would a scan pass?
A linear scan passes the tests for n ≤ 10⁴, but the prompt explicitly asks for O(log n). I'll mention the scan as a baseline and implement 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

Where candidates slip

Falling back to a linear scan to find the insertion point after binary search 'fails', or returning `-1`/`hi`/`mid` instead of `lo` — off-by-one at the boundary.

How to stand out

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 to frame the speed-up, then immediately pivot to binary search since the prompt demands O(log n).	Read
2	Lower-Bound Binary Search (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want. Describe the invariant ('answer stays in [lo, hi]') and the punchline ('lo is the insertion point after the loop') 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 to frame the speed-up, then immediately pivot to binary search since the prompt demands O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Ignore the sortedness for a moment — walk left to right. What's the first index where the array element is no longer smaller than the target?

2Hint 2Explore hint

The insertion point is the first index `i` with `nums[i] >= target`. Scan until you find it.

3Hint 3Explore hint

If you never find such an index, every element was smaller, so the answer is `n` (append at the end).

A · Core idea

Walk the array from the front and return the first index i where nums[i] >= target. If you reach the end without finding one, return n because the target is larger than everything.

B · Visual dry run

Interactive dry run

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

nums = [1, 3, 5, 6], target = 2

i=0

nums[0]=1 >= 2? no

Statecontinue

Final result1

C · Code with teaching comments

Reference implementation previewpublic int searchInsert(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 searchInsert(int[] nums, int target) {
2
    for (int i = 0; i < nums.length; i++) {
3
        // First element NOT smaller than target — handles found (==) and not-found (>)
4
        // in one test.
5
        if (nums[i] >= target) {
6
            return i;
7
        }
8
    }
9
    // Fell off the end → target exceeds everything → append at index n.
10
    return nums.length;
11
}

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

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

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

E · Edge cases and pitfalls3Comparing with `==` only — you'll miss the insertion point entirely when the target is absent.Explore edge cases

Pitfalls

Comparing with `==` only — you'll miss the insertion point entirely when the target is absent.
Forgetting the trailing `return n` for the 'larger than everything' case.
Submitting this when the prompt demands O(log n) — it passes but signals you ignored sortedness.

03.2

Approach 2 of 2 · Optimal

Lower-Bound Binary Search (Optimal)

TimeO(log n)SpaceO(1)

The answer they want. Describe the invariant ('answer stays in [lo, hi]') and the punchline ('lo is the insertion point after the loop') as you write it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The array is sorted, so you can binary search. The twist: the target might be absent, but you still owe an index. Where do the pointers end up when the search 'fails'?

2Hint 2Explore hint

Run the standard inclusive-bounds search. If `nums[mid] == target` return `mid`. Otherwise narrow the window exactly as in plain binary search.

3Hint 3Explore hint

When the loop exits, `lo` has crossed past every element smaller than the target — that count is precisely the insertion index. Return `lo`, no special case.

A · Core idea

B · Visual dry run

Interactive dry run

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

nums = [1, 3, 5, 6], target = 2

Array state

lo=0, hi=3

mid=1, nums[1]=3 > 2 → discard right half

lo ↓

[0]

mid ↓

[1]

[2]

hi ↓

[3]

Current pointerResolved stateNot processed

Final result1

C · Code with teaching comments

solution.javaJava

Lower-Bound Binary Search (Optimal) — optimal

6 teaching notes

1
public int searchInsert(int[] nums, int target) {
2
    // Inclusive window; hi is the LAST valid index.
3
    int lo = 0, hi = nums.length - 1;
4
    // The `=` keeps a one-element window alive so the last candidate is inspected.
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
        // Everything ≤ mid is too small → boundary is to the right → lo = mid + 1.
11
        } else if (nums[mid] < target) {
12
            lo = mid + 1;
13
        } else {
14
            // nums[mid] >= target → mid could be the boundary, but search left for an
15
            // earlier one.
16
            hi = mid - 1;
17
        }
18
    }
19
    // Loop exits with lo = count of elements < target = the insertion point. No special
20
    // case.
21
    return lo;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 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 `[lo, hi]`, so it runs in ⌈log₂(n+1)⌉ = O(log n) steps. Only scalar variables are used → O(1) space.

E · Edge cases and pitfalls8nums = [1, 3, 5, 6], target = 7 — Every element < 7, so lo keeps advancing until lo = 4 = n. Returns 4 (append at end).Explore edge cases

Edge cases handled

nums = [1, 3, 5, 6], target = 7Every element < 7, so lo keeps advancing until lo = 4 = n. Returns 4 (append at end).
nums = [1, 3, 5, 6], target = 0nums[mid] > 0 always, so hi keeps shrinking and lo never moves. Returns 0 (front).
nums = [1], target = 1mid=0, nums[0]==1 → return 0 immediately.
nums = [1], target = 0mid=0, 1 > 0 → hi=-1, loop ends, return lo=0.

Pitfalls

Returning `-1` for the not-found case — this problem wants an index, never -1.
Returning `hi` or `mid` instead of `lo` — `hi` is `lo - 1` after the loop, off by one.
Doing a linear scan after binary search 'fails' — defeats the O(log n) requirement.
Using `mid = (lo + hi) / 2` (overflow) or `while (lo < hi)` with inclusive bounds (skips the last element).

Practice

Try the solution yourself

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

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.

Returning the wrong pointer after the loop

When the loop exits, `hi` equals `lo - 1`. Returning `hi` gives an index one too small; only `lo` equals the count of elements below target (the insertion point).

Explore the code comparison

Don't write this

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

Write this instead

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

Returning -1 for a missing target

This is a copy of plain binary search where -1 means 'absent'. But Search Insert Position must return an index in every case — the insertion point, which is `lo`.

Explore the code comparison

Don't write this

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

Write this instead

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 lo

Overflow in the midpoint

In Java `lo + hi` is a 32-bit int; for large arrays it can exceed 2^31 − 1, wrap negative, and crash with ArrayIndexOutOfBoundsException. Use the difference form.

Explore the code comparison

Don't write this

int mid = (lo + hi) / 2;

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Lower-bound binary search — first index with nums[i] >= target

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 lo   # insertion point, no special case

Rules to remember

1After an inclusive-bounds loop exits, `lo` is the insertion point — the count of elements strictly less than target. Return it directly.
2Use mid = lo + (hi - lo) / 2, never (lo + hi) / 2 — the latter overflows int in Java for large indices.
3Loop with while (lo <= hi) and inclusive hi = n - 1; the = keeps the final one-element window alive.
4Always move past mid (lo = mid + 1 / hi = mid - 1) so the window strictly shrinks and the loop terminates.
5Returning lo (not hi or mid) is what makes this work — hi after the loop is lo - 1, one short.

Use this pattern when

Sorted array + 'where does X go?' / 'first index >= X' / 'insertion point'
You need a boundary, not just an exact match — the target may be absent
Counting elements less than a threshold in O(log n)
Any 'lower_bound' / 'ceil index' phrasing on monotonic data

Choose another pattern when

Array is unsorted → sort first (O(n log n)) or just scan, binary search needs order
You only ever need exact presence, never the position → a hash set is simpler
Duplicates with a 'first/last occurrence' twist → that's the boundary-search variant (LC 34), slightly different

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

Binary Search
The base template — return -1 when absent instead of the insertion point.
Find First and Last Position of Element in Sorted Array
Coming soon
Two boundary searches (lower_bound and upper_bound) to handle duplicates.
First Bad Version
Coming soon
Lower-bound search on a monotone predicate instead of array values.
Search in Rotated Sorted Array
Decide which half is sorted first, then binary search that half.

Same pattern

←

Find Peak Element

Continue · Next problem

Aggressive Cows