Search Insert Position

Difficulty: Easy

Problem

You are given an array of distinct integers sorted in ascending order and a target value. If the target is present, return its index; if it is missing, return the position at which it would have to be inserted to keep the array sorted. Your algorithm must run in O(log n) time.

Example

Input: nums = [2, 4, 7, 10, 15], target = 10
Output: 3
Explanation: 10 is found at index 3.

Brute-force approach

Scan the array from left to right. Return the index of the first element that is greater than or equal to the target. If no such element exists, return the array length.

Steps

  1. For each index i from 0 to n-1:
  2. If nums[i] >= target, return i
  3. If loop ends, return n (insert at end)

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Checks elements one by one: O(n) in the worst case
  • Doesn't leverage the sorted property
  • For large arrays, binary search is exponentially faster

Optimal approach

Key insight: Standard binary search, but when the target isn't found, the left pointer naturally lands on the correct insert position, the first element >= target.

Use binary search. If the target is found, return mid. If not found, left will be pointing to the correct insert position.

Steps

  1. Set left = 0, right = n - 1
  2. While left <= right:
  3. mid = left + (right - left) / 2
  4. If nums[mid] == target: return mid
  5. If nums[mid] < target: left = mid + 1
  6. If nums[mid] > target: right = mid - 1
  7. Return left (the insert position)

Time complexity: O(log n) · Space complexity: O(1)

Pseudocode

function searchInsert(nums, target):
    left = 0
    right = len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            return mid
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

Hints

  • This is binary search with a twist: when the target isn't found, left is the insert position
  • When the loop ends with left > right, left points to the first element >= target
  • The insert position is always where left ends up

Complexity questions

What is the time complexity of linear scan for insert position?

O(n). In the worst case (target larger than all elements), we scan the entire array, O(n).

What is the time complexity of the binary search approach?

O(log n). Binary search halves the search space each step, O(log n).

What is the space complexity of both approaches?

O(1). Both use only a constant number of variables, O(1) space.

Check your understanding of Search Insert Position

For nums = [1, 3, 5, 6] and target = 2, where should 2 be inserted?

Index 1 (between 1 and 3). 2 is greater than 1 but less than 3. To maintain sorted order, it must go at index 1, shifting 3, 5, 6 to the right.

If the target equals an element in the array, what do we return?

The index of that element. If the target is found, we simply return its index, same as regular binary search.

For nums = [1, 3, 5], target = 6, what is the insert position?

3. 6 is larger than all elements. It should be inserted at the end, at index 3 (which equals the array length).

Related problems

Keep practising