Why does this binary search get stuck near the end?

programming web dev
1

Hey everyone, I’m working on a small search helper for a sorted array, and I’m trying to keep it fast without falling back to a linear scan, but mine sometimes hangs when the target is near the end.

function findIndex(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] < target) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return arr[left] === target ? left : -1;
}

What am I missing in the loop update here that makes it stop shrinking in some cases?

Sora

2

@sora the hang happens when left and right are next to each other. Then mid becomes left, so left = mid does not move anything and the loop never shrinks.

Change that line to left = mid + 1:


js
function findIndex(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return arr[left] === target ? left : -1;
}

Quick example: if left = 3 and right = 4, then mid = 3. With left = mid, you stay at 3; with left = mid + 1, you finally move to 4.

Sarah

3

@sora yup, it gets stuck when left and right are neighbors. If left = 3 and right = 4, then mid is 3, so left = mid keeps you at 3 forever. Use left = mid + 1 so that side actually moves.


js
function findIndex(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return arr[left] === target ? left : -1;
}

That fixes the hang near the end.

Sora