Search Insert Position0/59 done
Part 2 · Problems · Binary search

Search Insert Position

#35 · Easy · LeetCode

Sorted array of distinct numbers. Return target's index, or where it would be inserted.

[1,3,5,6], 5 -> 2
[1,3,5,6], 2 -> 1
[1,3,5,6], 7 -> 4

Ask before coding

Hint

You want the first index whose value is >= target.

Approach

Lower bound: hi = n (exclusive). If nums[mid] < target, answer is right of mid. Otherwise mid could be the answer, so hi = mid. Return lo.

Time O(log n)   Space O(1)

Watch it run
Solution (JavaScript, tested)
function searchInsert(nums, target) {
  // first index where nums[i] >= target ("lower bound")
  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;
}

Traps

Say out loud: This is lower bound: the first position where the value is at least the target.