Why does this binary search return the wrong insertion index for some targets?

programming web dev
1

I’m writing a helper that should return the index of target if found, otherwise the position where it should be inserted to keep the array sorted. It works for some cases but fails near the ends. What is the bug in the loop/update logic?

function searchInsert(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo;
}
console.log(searchInsert([1,3,5,6], 5));
console.log(searchInsert([1,3,5,6], 2));

Sarah

2

Your loop is mixing a lower-bound pattern with a hi = mid - 1 update, so it can skip the correct insert spot at the left edge and it also can’t return nums.length for targets bigger than all items because hi starts too low.

BayMax