Search insert position

Easy TimeO(log n) SpaceO(1)

Given a sorted array nums of distinct values and a target, return the index where the target is — or, when it is absent, the index it would have to take for the array to stay sorted. A target below everything belongs at 0, and one above everything belongs one past the last index.

Examples

Example 1

Input
nums = [1, 3, 5, 6]target = 4
Output
2
4 is missing, and belongs between the 3 and the 5 — at index 2.

Example 2

Input
nums = [1, 3, 5, 6]target = 7
Output
4
7 is above everything, so it belongs at index 4, one past the last.

The Code

function searchInsert(nums, target) {
  let low = 0;
  let high = nums.length;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] < target) low = mid + 1;
    else high = mid;
  }
  return low;
}
searchInsert([1, 3, 5, 6], 4);
Done
Step through searchInsert([1, 3, 5, 6], 4) call by call

More like this

All searching examples (8) →