Skip to main content

6. Search Insert Position

easyAsked at Coinbase

Given a sorted array, find the index where a target should be inserted to maintain order. Coinbase asks this because it's the building block for inserting a new limit order at the right price level in an order book.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Coinbase loops.

  • Glassdoor (2026-Q1)— Coinbase order-book domain question.
  • Blind (2025-10)— Reported with a follow-up 'now insert into a sorted price ladder'.

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

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Examples

Example 1

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

Example 2

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

Example 3

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

Approaches

1. Linear scan

Walk the array until you find target or a value larger than target.

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

Tradeoff: Linear — prompt asks O(log n). Mention only as a baseline.

2. Binary search for lower-bound

Maintain [lo, hi) where lo is the smallest index with nums[lo] >= target. Loop until lo == hi; return lo.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Tradeoff: Classic lower-bound binary search. The half-open [lo, hi) invariant prevents the off-by-one bugs that plague closed-interval variants.

Coinbase-specific tips

Coinbase grades the lower-bound invariant — they want to see you articulate 'lo is the answer index, hi is the exclusive upper bound, mid is biased low.' Bonus signal if you mention that for an order book with millions of price levels, binary search beats a hash map because price levels are sparse and cache-friendly when stored contiguously.

Common mistakes

  • Using mid = (lo + hi) / 2 in a language with overflow — use (lo + hi) >>> 1 or lo + ((hi - lo) >> 1).
  • Using hi = nums.length - 1 with the closed-interval pattern but updating bounds for half-open — pick one style and stick with it.
  • Returning nums.length-1 when target exceeds all values — the answer is nums.length.

Follow-up questions

An interviewer at Coinbase may pivot to one of these next:

  • Allow duplicates — return the leftmost or rightmost insertion index.
  • Insert into a price ladder represented as a balanced BST.
  • What if the array is rotated?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why half-open [lo, hi)?

It unifies search and insert: when the loop ends, lo equals hi and that's the index. Closed intervals need a +1 fixup that's easy to forget.

How does this map to an order book?

Inserting a new limit order at a new price level is exactly this operation against a sorted ladder of price levels. Real engines use a skip list or RB-tree for amortized O(log n) inserts at scale.

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other Coinbase interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →