Why does this binary search miss the last matching index?

programming web dev
1

Hey everyone, I’m wiring up a quick search helper for a sorted list of order IDs, and I’m trying to return the last index of a target without scanning the whole array. The linear scan is safe but too slow for the hot path, and this version seems to fail right when duplicates sit at the end.

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

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

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

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

console.log(lastIndexOfTarget([1, 2, 2, 2], 2));

What am I getting wrong in this binary search update logic that makes it skip the correct last match?

Sarah

2

Your loop is finding the insertion point just after the last target, so when the duplicate run is at the end, left can step past the real answer. For the last occurrence, keep a matching mid in the search range and use a right-biased midpoint so the loop still makes progress.


js
function lastIndexOfTarget(nums, target) {
  if (nums.length === 0) return -1;

  let left = 0;
  let right = nums.length - 1;

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

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

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

For [1, 2, 2, 2] and 2, this returns 3 as expected.

Hari

3

Your binary search is currently doing an upper-bound search, not a direct “last matching index” search.

The issue is that an upper-bound version is allowed to move left past the final matching value. For the last occurrence, you want to keep a matching mid in play and bias mid to the right so left = mid still makes progress. That is why the duplicate-at-the-end case works with the adjusted midpoint.

The smallest fix is this:

while (left < right) {
  const mid = Math.floor((left + right + 1) / 2);
  if (nums[mid] <= target) {
    left = mid;
  } else {
    right = mid - 1;
  }
}

Tiny version of the same idea:

const mid = Math.floor((left + right + 1) / 2);

With mid biased right and left = mid kept in play:

  • + 1 makes sure adjacent left and right do not stall the loop.
  • left = mid preserves the current matching candidate instead of stepping past the last duplicate.

So the final nums[left] === target check is done on a real candidate index.

You can see left, right, and mid land on the tail duplicate here:

function lastIndexOfTarget(nums, target) {
  if (nums.length === 0) return -1;

  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right + 1) / 2);
    if (nums[mid] <= target) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }

  return nums[left] === target . left : -1;
}

console.log(lastIndexOfTarget([1, 2, 2, 2], 2)); // 3
console.log(lastIndexOfTarget([1, 2, 2, 3], 2)); // 2
console.log(lastIndexOfTarget([1, 3, 4], 2));    // -1

If you actually wanted the insertion point after the target run, the original upper-bound shape was the right one.

MechaPrime