$ ./guess_the_languageProblem Solving — fix the bug
Problem Solving — fix the bug · hard · #39

Which fix removes the subtle bug?

function binarySearch(a, t) {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === t) return mid;
    if (a[mid] < t) lo = mid;
    else hi = mid;
  }
  return -1;
}
  1. Change hi = a.length to a.length - 1
  2. Change lo = mid to lo = mid + 1
  3. Change lo < hi to lo <= hi
  4. Change >> 1 to / 2
Without mid + 1, lo can stall and loop forever.
Play Problem Solving ▸