Search Insert Position

Concept

LeetCode #35.
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.

Input: nums = [1,3,5,6], target = 5 -> Output: 2 (Found it).
Input: nums = [1,3,5,6], target = 2 -> Output: 1 (Not found, but 2 belongs between 1 and 3).

This problem is the foundational building block for “Binary Search on Answer”. It teaches you what happens to the Left and Right pointers when a standard Binary Search completely fails.

The Magic of the Left Pointer

If you run a standard Binary Search with while (left <= right), and the target does not exist in the array, the loop will eventually break.

The mathematical geometry of Binary Search guarantees exactly one outcome when the loop breaks:

• The Right pointer will have crossed over to the left side of the insertion point.
• The Left pointer will be sitting precisely on the exact index where the target belongs.

Because the Left pointer always aggressively steps forward (left = mid + 1) when the value is too small, it fundamentally acts as a floor, guaranteeing it will come to rest exactly at the first value that is strictly greater than the target.

Implementation

The code is literally the exact same standard Binary Search template.
The only difference is the final return statement. Instead of returning -1 when the target is not found, you simply return the Left pointer.

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        // Prevents Integer Overflow
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid; // Target found!
        } else if (nums[mid] < target) {
            // Mid is too small. Target belongs on the right.
            left = mid + 1;
        } else {
            // Mid is too big. Target belongs on the left.
            right = mid - 1;
        }
    }

    // The loop broke! Target was not found.
    // The Left pointer is mathematically guaranteed to be at the exact insertion index.
    return left;
}

Interview Questions

Q: What if the target is larger than every single number in the array? (e.g., nums = [1,2,3], target = 5). Will the Left pointer crash with an out-of-bounds error?
A: No, it will not crash, but it will point out of bounds!

1. The loop checks the 3. It is too small.
2. left = mid + 1. Left moves to index 3.
3. Left (3) is now greater than Right (2). The loop breaks safely.
4. The function returns 3.
   Index 3 is exactly where the 5 belongs! If you were to array.push(5), it would land perfectly at index 3. The math is flawless.

Q: A developer suggests replacing while (left <= right) with while (left < right) to optimize the loop. How does this break the algorithm?
A: If you remove the =, the loop terminates early when left and right collide. At this point, the pointer hasn’t actually evaluated the final remaining element. Therefore, you don’t know if the target belongs before the element or after it. The mathematical guarantee that Left represents the insertion point is completely destroyed. Stick to the standard <= template.