Search Insert Position

The briefingthe full drill, in my own words

The drill: Find the index where a target either sits inside a sorted array or would need to be inserted to keep it sorted — the array holds distinct values in ascending order.

A sorted array of distinct integers arrives along with a target value, and the drill wants the index where that target belongs.

When the target already appears in the array, its own index is the answer. When it doesn't, the answer is the index it would need to occupy to keep the array in ascending order — sliding everything from that point onward one step to the right.

That insertion point is always well defined, including the two edge cases of inserting before the first element or after the last one.

array length can reach into the tens of thousands
values are distinct and arranged in ascending order
target may fall before the first or after the last element
answer is a single index, hit or insertion point alike

EX 01

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

→ 2

exact hit

EX 02

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

→ 1

insert between two values

EX 03

nums = [1, 3, 5, 6] · target = 7

→ 4

insert past the end

The hintstake only what you need

HINT 1 THE NUDGE

If the target isn't in the array, the answer is still a single specific index — the one spot ordering demands it slot into. What determines that spot?

HINT 2 THE STRUCTURE

The insertion index is exactly the count of elements smaller than the target — find the first position whose value is not less than target.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search for the leftmost index where nums[mid] >= target; when the loop ends, lo is that boundary — hit or insertion point alike.

Coach's boardthe pattern, step by step

THE LOWER BOUNDPATTERN · LOWER BOUND SEARCHnums = [-5, -3, -1, 2, 4, 8] · target = 3

-5

-3

-1

STEP 1

Target 3 isn't required to exist — only its correct slot does. Search window starts as the whole array, indices 0 to 5.

STEP 1 / 8 · ← → WORK TOO

The splitstwo paces, two languages

grind/search-insert-position.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 10 LN

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i, v in enumerate(nums):
            if v >= target:
                return i
        return len(nums)

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 6 LN

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 14 LN

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 10 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED