Search Insert Position

Find the first legal position, not merely a matching value.

Read the contract as an insertion problem

The obvious version of binary search asks:

Does the target exist, and if so, where?

This problem asks for more. If the target is absent, return the index where it could be inserted while keeping the array sorted.

For nums = [1, 3, 5, 6]:

Target	Result	Reason
5	2	5 already exists at index 2
2	1	Insert between 1 and 3
7	4	Insert after the final element

That last result matters. The answer can equal len(nums), even though that is not an existing element index. The returned value represents a position between elements, so the position after the last element is valid.

A left-to-right scan would solve the problem:

for i, value in enumerate(nums):
    if value >= target:
        return i
return len(nums)

But that takes O(n) time in the worst case. The array is already sorted, and the contract requires O(log n). The sorted order is the leverage: each comparison should eliminate about half of the remaining positions.

The useful direction is:

Search for the first index whose value is greater than or equal to target.

That boundary is the insertion index.

Recognize the lower-bound boundary

Instead of treating the task as exact lookup, ask a yes-or-no question at every index:

nums[i] >= target

Because nums is sorted, the answers have a predictable shape:

False, False, False, True, True, True

The False positions contain values smaller than the target. The first True position is the first place where the target can stand without breaking ascending order.

This first valid position is called the lower bound.

For example, with:

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

the predicate produces:

index:  0      1      2     3
value:  1      3      5     6
valid: False  False  True  True

The lower bound is index 2. Inserting 4 there gives [1, 3, 4, 5, 6].

This model also handles an existing target. For target = 5, index 2 is the first index where nums[i] >= 5. Equality does not require a separate idea. It is already part of the boundary condition.

That is the important shift:

• Exact search asks whether nums[mid] == target.
• Insertion search asks whether nums[mid] is the first value that is not too small.

The brute-force scan checks those positions one by one. Binary search checks the monotonic boundary and discards half of the remaining candidates after each comparison.

Derive the half-open interval

Use a half-open search interval:

[left, right)

The left endpoint is included. The right endpoint is excluded.

Initialize:

left = 0
right = len(nums)

Why should right start at len(nums) instead of len(nums) - 1?

Because len(nums) is a valid insertion position when the target is larger than every array value. Making the right boundary exclusive includes that position naturally. We do not need a special append case later.

Maintain this invariant:

The required insertion index remains somewhere in [left, right). Every index before left is known to contain a value smaller than target. Every index at or after right is known to be at or beyond the first valid boundary.

At each step, inspect:

mid = (left + right) // 2

There are only two meaningful cases.

Case 1: nums[mid] < target

The midpoint is too small. Because the array is sorted, every index before mid is also too small. None of those positions can be the answer.

Discard them:

left = mid + 1

Case 2: nums[mid] >= target

The midpoint is a valid insertion position. It might be the first one, so we must keep it as a candidate.

Discard only positions after it:

right = mid

Do not use right = mid - 1 here. That would remove mid, even though mid may be the answer.

The loop stops when:

left == right

The half-open interval is empty, and the converged position is the first index whose value is at least target. If every value is smaller, that position is len(nums).

Trace the pointers before coding

Take:

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

The first valid position is index 1, because 2 belongs between 1 and 3.

left	right	mid	nums[mid]	Decision
0	4	2	5	5 >= 2, keep mid: right = 2
0	2	1	3	3 >= 2, keep mid: right = 1
0	1	0	1	1 < 2, discard through mid: left = 1

Now left == right == 1. Return 1.

The algorithm never needed to insert anything. It only located the boundary where insertion would be legal.

Existing target

For target = 5:

1. The midpoint may land on index 2.
2. Since nums[2] >= 5, set right = 2.
3. The search continues to verify that no earlier index also satisfies the condition.
4. The interval converges to 2.

With distinct values, that is the target's only index. More generally, continuing after equality is what makes this a lower-bound search rather than a simple exact lookup.

Target after the final element

For target = 7:

nums = [1, 3, 5, 6]

The pointer movement is:

[0, 4) -> [3, 4) -> [4, 4)

Every array value is smaller than 7, so left advances to 4. Returning 4 correctly represents insertion after the final element.

Singleton arrays

The same interval handles all one-element cases:

nums	target	Result
[5]	2	0
[5]	5	0
[5]	8	1

The result is either before the element, at the element, or after it. No special branch is necessary.

Implement the lower bound in Python

from typing import List


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)

        while left < right:
            mid = (left + right) // 2

            if nums[mid] < target:
                # mid and everything before it are too small.
                left = mid + 1
            else:
                # mid may be the first valid position.
                right = mid

        return left

Each variable has a direct obligation:

• left excludes positions proven too small.
• right preserves the first possible valid boundary.
• mid is the position used to split the remaining interval.
• left == right means only one boundary position remains.

Notice that there is no return mid equality branch. Equality is handled by the else branch because nums[mid] >= target means “this position is valid, but an earlier valid position may exist.”

A closed-interval binary search can also solve this problem with right = len(nums) - 1 and while left <= right. That template is valid, but mixing its updates with the half-open version causes common off-by-one errors:

• right = mid - 1 belongs to a closed interval when mid is rejected.
• right = mid belongs to this half-open lower-bound search because mid remains a candidate.
• right = len(nums) is intentional here because the answer may be len(nums).

Pick one interval convention. Write down what each boundary means. Do not blend templates from memory.

In Python, the library equivalent is:

from bisect import bisect_left

index = bisect_left(nums, target)

That is useful in production code when the library is allowed. In an interview, derive the manual lower-bound version first. The value is not merely producing an index; it is showing that you understand why the index is correct.

Why the algorithm is correct

Let n = len(nums).

Initialization

The initial interval is [0, n).

Every possible insertion position is inside it:

• 0 means before the first element.
• Any interior index means between two elements.
• n means after the final element.

So the required answer is included before the first iteration.

Preserving the invariant

Suppose mid = (left + right) // 2.

If:

nums[mid] < target

then every index at or before mid contains a value smaller than target, because the array is sorted. Therefore none of those positions can be the first index with nums[i] >= target. Setting left = mid + 1 removes only impossible positions.

Otherwise:

nums[mid] >= target

Then mid is a valid insertion position. The answer might be mid, or it might be earlier. Setting right = mid keeps mid and every position before it while discarding positions after the current candidate boundary.

In both cases, the answer remains inside [left, right).

Termination

Each iteration makes the interval smaller:

• left moves forward past mid, or
• right moves back to mid.

Eventually left == right. Every earlier index has been proven too small, and the converged position is the first index with nums[i] >= target. If no such array index exists, the position is n.

Therefore, returning left satisfies both parts of the contract:

• it returns the existing target index when present;
• it returns the correct insertion index when absent.

Complexity

Each comparison cuts the remaining interval roughly in half. Starting with n possible positions takes O(log n) iterations to reduce to one position.

The algorithm stores only left, right, and mid, so its auxiliary space is O(1).

The result is:

Time:  O(log n)
Space: O(1)

Test the edges that expose off-by-one errors

Before trusting a binary search, test the boundaries deliberately:

tests = [
    ([1, 3, 5, 6], 0, 0),  # before the first value
    ([1, 3, 5, 6], 1, 0),  # exact first value
    ([1, 3, 5, 6], 4, 2),  # between two values
    ([1, 3, 5, 6], 5, 2),  # exact interior value
    ([1, 3, 5, 6], 7, 4),  # after the final value
    ([1], 0, 0),           # singleton, before
    ([1], 1, 0),           # singleton, exact
    ([1], 2, 1),           # singleton, after
]

The supplied contract guarantees a nonempty array with distinct values, so the main solution does not need to solve the duplicate case.

Still, the boundary idea is worth noticing. If duplicates were allowed, returning immediately on the first equality would not necessarily return the first valid position. A lower-bound search keeps equality as a candidate and continues left. That is the broader pattern, even though distinct inputs make either exact-match location acceptable here.

Watch for three implementation failures:

1. Reading nums[mid] after the interval is empty.
   The loop condition left < right prevents this.

2. Removing mid when it is valid.
   Use right = mid when nums[mid] >= target.

3. Forgetting the end position.
   Start with right = len(nums), not len(nums) - 1, when using this half-open form.

The reusable recognition rule

When a sorted domain turns a condition into a sequence like:

False, False, ..., True, True

search for the first true position.

For this problem, that means:

• use an exclusive right boundary;
• preserve mid when nums[mid] >= target;
• move past mid only when nums[mid] < target;
• return left after convergence.

The durable skill is not memorizing one Search Insert Position solution. It is learning to turn an insertion contract into a boundary, then letting the invariant drive the code.