Search Insert Position

EasyBinary Search · Lower Bound🧩 Binary Search LeetCode #35 ↗Updated Oct 30, 2026

Problem

You get a sorted array nums of distinct integers and a value target. Return the index of target if it is present; otherwise return the index where it would have to be inserted so the array stays sorted. Aim for O(log n) time.

Inputnums = [1,3,5,6], target = 5Output2

Inputnums = [1,3,5,6], target = 2Output1

Inputnums = [1,3,5,6], target = 7Output4

1 ≤ n ≤ 10⁴ · -10⁴ ≤ nums[i], target ≤ 10⁴ · nums sorted ascending, distinct · O(log n) required

Try it yourself

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Both cases have the same answer: the first index whose value is ≥ target (the lower bound). That predicate is false…false, true…true across the array, so binary search can find the boundary directly.

PatternBinary Search

Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.

Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.

Open the Binary Search guide →

Approaches

Brute ForceLinear Scan for First ≥ target

Time O(n)Space O(1)

Walk left to right and stop at the first element that is not smaller than target — that is either the match or the slot it belongs in. If no such element exists, the target goes after everything, at index n.

Java

public int searchInsert(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] >= target) return i; // first slot that can hold target
    }
    return nums.length; // target is larger than every element
}

Correct and tiny, but ignores sortedness and misses the O(log n) requirement.

OptimalBinary Search on the Lower Bound

Time O(log n)Space O(1)

Keep a half-open window [lo, hi) that always contains the answer, starting with hi = n so “insert at the end” is reachable. If nums[mid] < target, mid and everything left of it are too small; otherwise mid might be the answer, so keep it. When the window closes, lo is the first index with value ≥ target.

Java

public int searchInsert(int[] nums, int target) {
    int lo = 0, hi = nums.length; // answer always lies in [lo, hi]
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) lo = mid + 1; // mid and its left side are too small
        else hi = mid;                        // mid may be the answer, keep it
    }
    return lo;
}

Dry runnums = [1,3,5,6], target = 5

lo low endm midhi high end (exclusive) changed

lo=0 hi=7
1
lo
3

5

6
m
8

10

12

6 < 7 → lo=4
lo=4 hi=7
1

3

5

6

8
lo
10
m
12

10 ≥ 7 → hi=5
lo=4 hi=5
1

3

5

6

8
lo m
10
hi
12

8 ≥ 7 → hi=4
lo=hi=4
1

3

5

6

8
lo hi
10

12

insert 7 at 4 ✔

Logarithmic, no special cases — the same template solves every lower-bound question.

Pro tip

Use hi = n (not n - 1) so the “bigger than everything” case needs no extra check after the loop.

At a glance

Level	Approach	Time	Space
Brute Force	Linear Scan for First ≥ target	`O(n)`	`O(1)`
Optimal	Binary Search on the Lower Bound	`O(log n)`	`O(1)`

Common pitfalls

Starting with hi = n - 1 and forgetting the “insert at the end” case.
Writing hi = mid - 1 in the lower-bound template — can skip the answer.
Computing (lo + hi) / 2 carelessly; prefer lo + (hi - lo) / 2.

Interview tips

Reframe both cases as “first index with value ≥ target” before coding.
State the loop invariant: the answer always stays inside [lo, hi].
Mention that Java’s Arrays.binarySearch encodes the insert point as -(pos) - 1.

Pattern

Lower-bound binary search → sorted data plus “first position where a condition becomes true”.

My notes saved in this browser