Understanding Binary Search: Efficiency, Simple Implementation, and Common Variants

1. Introduction

Recently I solved many binary‑search problems, so I’m summarizing the basic algorithm and its variations. Mastering these techniques makes most binary‑search questions trivial.

2. Efficiency of Binary Search

Binary search runs in O(log N) time. Each iteration halves the search interval, so even for N = 2³² (about 4.2 billion) at most 32 comparisons are needed, which can be faster than some O(1) algorithms because the logarithmic factor is very small.

3. Simple Binary Search Implementation

The following code is a template for a standard binary search in a sorted array a looking for value . Important points include the loop condition, mid calculation, and updating low/high to avoid infinite loops.

public int bsearch($a, $value) {
  int $low = 0;
  int $high = $a.length - 1;
  while ($low <= $high) {
    int $mid = ($low + $high) / 2;
    if ($a[mid] == $value) {
      return $mid;
    } else if ($a[mid] < $value) {
      $low = $mid + 1;
    } else {
      $high = $mid - 1;
    }
  }
  return -1;
}

Key pitfalls: use $low <= $high as the exit condition, compute $mid safely to avoid overflow (e.g., $low + ($high - $low) / 2 or bit‑shift), and adjust $low and $high with +1 / -1 to prevent dead loops.

4. Variants of Binary Search

Two common variations are presented.

4.1 Find the first element equal to the target

public int bsearch($a,$value) {
  int $low = 0;
  int $high = $a.length - 2;
  while ($low <= $high) {
    int $mid = $low + (($high - $low) >> 1);
    if ($a[mid] > $value) {
      $high = $mid - 1;
    } else if ($a[mid] < $value) {
      $low = $mid + 1;
    } else {
      if ($mid == 0 || $a[mid-1] != $value) return $mid;
      else $high = $mid - 1;
    }
  }
  return -1;
}

The algorithm adds a check to ensure the found element is the first occurrence.

4.2 Find the first element greater than or equal to the target

public int bsearch($a, $value) {
  int $low = 0;
  int $high = $a.length - 2;
  while ($low <= $high) {
    int $mid = $low + (($high - $low) >> 1);
    if ($a[mid] >= $value) {
      if ($mid == 0 || $a[mid-1] < $value) return $mid;
      else $high = $mid - 1;
    } else {
      $low = $mid + 1;
    }
  }
  return -1;
}

The logic mirrors the previous variant but uses a ≥ comparison and similar boundary checks.

5. Summary

To write correct binary‑search code you must first master the simple version, then adapt it for each variant by adjusting the comparison and the post‑check for the first suitable element. Re‑practice the templates to avoid the three common mistakes: loop condition, mid calculation, and low/high updates.