LeetCode 35: Search Insert Position. Binary Search vs Linear Scan

The Problem

Given a sorted array of distinct integers and a target value, return the index where the target would be inserted to maintain order. If the target already exists, return its index.

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

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

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

The problem is straightforward on the surface, but the constraints reveal its intent. The array is sorted, and the operation needs to complete efficiently.

---

A Linear Solution

A linear scan checks each element until we find the insertion point.

var searchInsert = function(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
  }
  return nums.length;
};

This works but runs in O(n) time. For an array of 10,000 elements, the worst case iterates through all of them. The problem expects a solution that exploits the fact that the input is sorted.

---

Binary Search

Binary search divides the search space in half at each step. It runs in O(log n) time, which means finding an element in a million entries takes at most 20 comparisons instead of a million.

The algorithm maintains three pointers: left, right, and mid. At each step we check the middle element. If it matches the target, we are done. If the target is smaller, we discard the right half. If larger, we discard the left half.

When the loop ends without finding the target, left points to where the target should be inserted.

var searchInsert = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;

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

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

  return left;
};

---

Why the Insertion Point Works

When the loop exits, left has crossed right. The element at left is the first element greater than the target (or left equals the array length if the target belongs at the end). This is exactly the insertion position.

The invariant nums[right] < target < nums[left] holds at the point of exit. Visualizing this helps. Try tracing through [1, 3, 5, 6] with target = 2:

Step 1: left=0, right=3, mid=1, nums[1]=3 > 2, go left
Step 2: left=0, right=0, mid=0, nums[0]=1 < 2, go right
Step 3: left=1, right=0, exit loop, return left=1

The index 1 is where 2 fits between 1 and 3.

---

Edge Cases

Target smaller than all elements. The algorithm returns 0, which is correct.

nums = [10, 20], target = 5
left=0, right=1, mid=0, nums[0]=10 > 5, right=-1, exit, return 0

Target larger than all elements. The loop shifts left past the last index and returns nums.length.

nums = [10, 20], target = 30
left=0, right=1, mid=0, nums[0]=10 < 30, left=1
left=1, right=1, mid=1, nums[1]=20 < 30, left=2
exit, return 2

Single element arrays. The algorithm handles these with no special cases.

nums = [5], target = 3
left=0, right=0, mid=0, nums[0]=5 > 3, right=-1, exit, return 0

---

Complexity

Approach	Time	Space
Linear scan	O(n)	O(1)
Binary search	O(log n)	O(1)

Binary search matches the problem's constraints and is the expected solution. The space complexity is constant because we only store three integers regardless of input size.

---

Takeaways

Binary search is one of those patterns that seems trivial on paper but requires careful pointer management in practice. The off by one errors are common. The key is tracking the invariant: the condition for moving left and right must be consistent, and the exit condition must guarantee that left is the answer.

Practice this pattern on a few variations:

• Standard binary search (find exact match)
• Lower bound (first position where element could be inserted)
• Upper bound (last position where element could be inserted)

Each variant adjusts the pointer movement rules slightly. Understanding one makes the others click.