Search Insert Position

Difficulty: Easy

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 inserted in order. You must write an algorithm with O(log n) runtime complexity.

Example

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 is found at index 2.

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)