Efficient Search and Insertion in Sorted Arrays: Algorithm

Here's a common interview problem: given a sorted array, find where a target value is — or where it should be inserted to keep the array sorted.

This is a classic binary search variant. Instead of returning -1 when the target isn't found, you return the insertion index.

The Problem

Given a sorted array and a target, return the index if found. If not, return the index where it would be inserted in order.

The Code

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

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

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return left;
}

console.log(searchInsert([1, 3, 5, 6], 5)); // 2 (found)
console.log(searchInsert([1, 3, 5, 6], 2)); // 1 (insert here)
console.log(searchInsert([1, 3, 5, 6], 7)); // 4 (insert at end)
console.log(searchInsert([1, 3, 5, 6], 0)); // 0 (insert at start)

Why left Is the Answer

When the loop ends without finding the target, left always points to the first element that's greater than the target. That's exactly the insertion point.

The loop narrows the window until left > right. At that moment, everything before left is smaller than the target. Everything from left onward is larger. That's the insertion position.

Complexity

• Time: O(log n) — standard binary search.
• Space: O(1) — no extra allocation.

The Trade-off

This works perfectly for static or rarely-changing arrays. But if you're inserting frequently, shifting elements to maintain sort order is O(n) per insert. For dynamic data with frequent inserts and lookups, a balanced BST or a skip list would be a better fit.