Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Search Insert Position

Find the index of a target in a sorted array, or the index where it should be inserted, using the lower-bound form of binary search in O(log n).

easyPattern: Binary Search

Updated Short read: 4 min read

Approaches at a glance

ApproachTimeSpace
Linear scanO(n)O(1)
Binary search (lower bound)O(log n)O(1)

The problem

You are given an array of distinct integers sorted in ascending order, and a target. If the target is in the array, return its index. If it is not, return the index where it would have to be inserted to keep the array sorted. The solution must run in O(log n) time.

numbers = [1, 3, 5, 6], target = 5   →  2    (found)
numbers = [1, 3, 5, 6], target = 2   →  1    (between 1 and 3)
numbers = [1, 3, 5, 6], target = 7   →  4    (after everything)
numbers = [1, 3, 5, 6], target = 0   →  0    (before everything)

Restating the question

Both cases have the same answer: the index of the first element that is greater than or equal to the target.

  • If the target is present, that element is the target itself.
  • If it is absent, that element is the one the target must be placed in front of.
  • If no element is large enough, the answer is the array's length.

This value is called the lower bound, and finding it is one search rather than two cases.

Approach 1: linear scan

JavaScript

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

Python

def search_insert_linear(numbers, target):
    for i, value in enumerate(numbers):
        if value >= target:
            return i
    return len(numbers)

Time O(n). Space O(1).

Approach 2: binary search for the lower bound

JavaScript

function searchInsert(numbers, target) {
  let lo = 0;
  let hi = numbers.length;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (numbers[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

Python

def search_insert(numbers, target):
    lo = 0
    hi = len(numbers)
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if numbers[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

This differs from the exact-match binary search in three connected ways:

  1. hi starts at numbers.length, one past the last index, because "after everything" is a possible answer.
  2. The loop runs while lo < hi and ends when the two meet. That meeting point is the answer.
  3. hi = mid, not mid - 1. When numbers[mid] is greater than or equal to the target, mid might be the answer, so it stays in the range.

When numbers[mid] is less than the target, mid and everything before it are too small, so lo moves to mid + 1.

Walkthrough

numbers = [1, 3, 5, 6], target = 2:

lo hi mid numbers[mid] Action
0 4 2 5 5 ≥ 2, so hi = 2
0 2 1 3 3 ≥ 2, so hi = 1
0 1 0 1 1 < 2, so lo = 1
1 1 lo equals hi: return 1

Time O(log n). Space O(1).

Both templates are compared in the binary search pattern.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(searchInsert([1, 3, 5, 6], 5)); // 2
console.log(searchInsert([1, 3, 5, 6], 2)); // 1
console.log(searchInsert([1, 3, 5, 6], 7)); // 4

Python

print(search_insert([1, 3, 5, 6], 5))  # 2
print(search_insert([1, 3, 5, 6], 2))  # 1
print(search_insert([1, 3, 5, 6], 7))  # 4

The comment after each line is the result you should see.

Common mistakes

  • Starting hi at numbers.length - 1. A target larger than every element would then never get the answer numbers.length.
  • Using hi = mid - 1 in this version. That can discard the answer.
  • Handling "found" and "not found" separately. It works, but it is more code and more places for an off-by-one error.

Original problem: LeetCode 35: Search Insert Position