Binary search

In plain English

Binary search finds a value by repeatedly looking at the middle of a sorted range and discarding the half that cannot contain the target. It only works on sorted data, because the sorted order is what tells you which half to throw away. The midpoint is the index halfway between the low and high bounds, and after comparing you shrink the range by moving one of the bounds past it. Off-by-one errors happen when the loop condition or the bound update is one step too far, so the search skips the answer or runs forever. The lower bound is the first position where the value is not smaller than the target, and the upper bound is the first position where it is greater, which are handy for finding insertion points and ranges.

Step by step

1. 1Check that the input is sorted and set the low and high bounds.
2. 2Compute the midpoint and compare it with the target.
3. 3Move low or high past the midpoint based on the comparison.
4. 4Return -1 when the bounds cross without finding the target.
5. 5Adapt the loop into a lower bound that returns an insertion position.

function binarySearch(sorted, target) {
  let low = 0
  let high = sorted.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (sorted[mid] === target) return mid
    if (sorted[mid] < target) low = mid + 1
    else high = mid - 1
  }
  return -1
}

function lowerBound(sorted, target) {
  let low = 0
  let high = sorted.length
  while (low < high) {
    const mid = Math.floor((low + high) / 2)
    if (sorted[mid] < target) low = mid + 1
    else high = mid
  }
  return low
}

console.log(binarySearch([1, 3, 5, 7, 9], 7))
console.log(lowerBound([1, 3, 3, 3, 5], 3))

Common mistakes

• Writing mid = (low + high) / 2 with integers can overflow for very large arrays, so prefer low + (high - low) / 2 in other languages.
• Updating high = mid instead of high = mid - 1 can leave the search stuck when the target is not present.
• Forgetting that the input must be sorted makes binary search return wrong answers, because the half it discards might have contained the target.
• Using low < high with an inclusive high bound can skip the last element, which is a classic off-by-one error.