LC 35 — Search Insert Position

Problem

What are we solving?

Problem Statement

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be inserted to keep the array sorted. You must write an algorithm with O(log n) runtime complexity.

Example 1

Input:nums = [1, 3, 5, 6], target = 5

Output:2

Example 2

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

Output:1

Example 3

Input:nums = [1, 3, 5, 6], target = 7

Output:4

Intuition

Converting to a First True boundary problem

This is the cleanest possible introduction to the First True pattern. The key insight is that the question "where does target belong?" is identical to "what is the first index where the value is at least as large as the target?"

The insertion position is the first index where nums[i] >= target. Everything before it is too small. Everything from it onwards is large enough.

This flips the array into a boolean sequence. Let's visualise it:

Array: [1, 3, 5, 6] · Target = 5

condition: nums[i] >= target (5)

i=01

i=13

i=25

i=36

First T is at index 2 — that's where 5 lives, or where 5 would be inserted.

Array: [1, 3, 5, 6] · Target = 2 (not present)

condition: nums[i] >= target (2)

i=01

i=13

i=25

i=36

First T is at index 1 — that's where 2 would be inserted (between 1 and 3).

Array: [1, 3, 5, 6] · Target = 7 (beyond all elements)

condition: nums[i] >= target (7)

i=01

i=13

i=25

i=36

All F — boundary = 4 (one past the end). The template returns left = 4 naturally, no special case needed.

Step-by-step walkthrough

Array: [1, 3, 5, 6], target = 2

1

left=0, right=3 → mid=1, nums[1]=3

Is 3 >= 2? Yes → condition TRUE. Save boundary=1, search left: right = mid-1 = 0.

2

left=0, right=0 → mid=0, nums[0]=1

Is 1 >= 2? No → condition FALSE. Search right: left = mid+1 = 1.

3

left=1 > right=0 → loop ends

Return boundary = 1. Correct — 2 would be inserted at index 1.

→

Why this handles "target found" automatically: When nums[mid] == target, the condition nums[mid] >= target is still true, so we save it as the boundary and search left. We end up at the exact index of the target. No separate equality check needed.

Solution

Clean implementation

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int boundary = nums.length; // default: insert at end

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] >= target) {
                // condition TRUE: mid could be the answer
                boundary = mid;
                right = mid - 1; // search left for an earlier match
            } else {
                // condition FALSE: answer must be to the right
                left = mid + 1;
            }
        }

        return boundary;
    }
}

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        boundary = len(nums)  # default: insert at end

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

            if nums[mid] >= target:
                # condition TRUE: mid could be the answer
                boundary = mid
                right = mid - 1  # search left for an earlier match
            else:
                # condition FALSE: answer must be to the right
                left = mid + 1

        return boundary

Complexity

Time

O(log n)

We halve the search space every iteration.

Space

O(1)

Only three integer pointers — no extra memory needed.

→

Pattern connection: This is the lower bound in many standard libraries — Arrays.binarySearch in Java and bisect_left in Python implement this exact logic. Knowing this pattern means you understand what those library functions do internally.