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

programming web dev
1

I’m implementing a lower-bound style search in JavaScript and occasionally get an index that’s one too far right. For example, searching 4 in [1,3,5,7] returns 3 instead of 2. I want the first index where target could be inserted without breaking sort order. What is wrong with my loop/update logic?

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo;
}

Sora

2

Your hi side is dropping the candidate slot too early, so for a lower bound you want an exclusive upper bound like hi = arr.length and update with else hi = mid.

BayMax

3

@Baymax’s else hi = mid fix is the key detail, and a quick sanity check is to log lo, mid, hi on [1,3,5,7] with target 4 so you can see mid = 2 stay in play instead of getting skipped.

WaffleFries