Search Insert Position

Problem

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 if it were inserted in order.

Examples

The brute-force approach

Scan left to right. The moment you find a value that's >= target, that's your answer, either target is there, or that's where it would be inserted.

for i in 0 .. len(nums) - 1:
    if nums[i] >= target:
        return i       # found it or found the insertion point

return len(nums)       # target is larger than everything

Linear scan is O(n). For a sorted array, that's leaving half the available information on the table, the problem is set up perfectly for binary search.

Spotting the pattern

This is a Binary Search problem. The key question to ask yourself:

If the target isn't in the array, how do I know exactly where it would go?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.