Binary Search Explained Step by Step (with JavaScript Code)

 Binary search is usually the first "real" algorithm people learn in DSA, and for good reason: it's simple, it's fast, and it teaches the core idea behind a huge number of more advanced algorithms — solve a big problem by repeatedly cutting it in half.

It's also deceptively hard to write correctly. A famous study by Jon Bentley found that roughly 90% of professional programmers failed to write a bug-free binary search when given a couple of hours to do it. The algorithm is five lines; the edge cases are where everyone trips.

---

The Problem It Solves

You have a sorted list of numbers and you want to know if a target value exists in it (and where). The naive approach — checking every element one by one — is O(n). Binary search does it in O(log n), which is dramatically faster for large lists.

The difference is not subtle:

• 1,000 items: linear search ~1,000 comparisons, binary search ~10

• 1,000,000 items: linear search ~1,000,000 comparisons, binary search ~20

• 1,000,000,000 items: linear search ~1 billion comparisons, binary search ~30

Multiplying the data by 1,000 adds only 10 comparisons. That's what logarithmic growth means in practice.

---

How It Works

1. Look at the middle element of the list.

2. If it matches the target, you're done.

3. If the target is smaller, repeat the search on the left half.

4. If the target is larger, repeat the search on the right half.

5. Keep going until you find it, or the range becomes empty (not found).

Every step throws away half the remaining list — that's why it's so fast.

---

A Concrete Walkthrough

Searching for 14 in [1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24] (13 items, indexes 0–12):

Step 1: low=0, high=12, mid=6  → arr[6]=10   10 < 14, go right
Step 2: low=7, high=12, mid=9  → arr[9]=18   18 > 14, go left
Step 3: low=7, high=8,  mid=7  → arr[7]=13   13 < 14, go right
Step 4: low=8, high=8,  mid=8  → arr[8]=14   found, return 8

Four comparisons instead of nine. Trace this by hand once on paper — it's the fastest way to make the algorithm stick.

---

JavaScript Implementation (Iterative)

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

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid; // found it
    } else if (arr[mid] < target) {
      low = mid + 1; // search the right half
    } else {
      high = mid - 1; // search the left half
    }
  }

  return -1; // not found
}

const sortedNums = [1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24];
console.log(binarySearch(sortedNums, 14)); // 8
console.log(binarySearch(sortedNums, 5));  // -1

---

The Recursive Version

function binarySearchRec(arr, target, low = 0, high = arr.length - 1) {
  if (low > high) return -1;              // base case: empty range

  const mid = low + Math.floor((high - low) / 2);

  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    return binarySearchRec(arr, target, mid + 1, high);
  }
  return binarySearchRec(arr, target, low, mid - 1);
}

It reads more cleanly, but it uses O(log n) stack space instead of O(1). The iterative version is what you want in production code, and what most interviewers expect by default.

---

The Overflow Bug Hiding in (low + high) / 2

Notice the recursive version uses low + (high - low) / 2 instead of (low + high) / 2. The two are mathematically identical but not computationally identical.

In languages with fixed-width integers — Java, C, C++, Go, Rust — low + high can overflow past the maximum integer value when both are large, producing a negative number and an array-out-of-bounds crash. This bug sat undetected in the JDK's own binary search for nine years before it was found in 2006.

// Unsafe in Java/C/C++ for very large arrays:
int mid = (low + high) / 2;

// Safe everywhere — the subtraction can never overflow:
int mid = low + (high - low) / 2;

JavaScript numbers are 64-bit floats, so you won't hit this in JS in practice. Write it the safe way anyway — it costs nothing, and interviewers who know the history will notice.

---

Why the Array Must Be Sorted

Binary search only works because a sorted array guarantees that everything to the left of the middle is smaller, and everything to the right is bigger. That guarantee is what lets you safely discard half the list every time. Run it on an unsorted array and it will give you wrong answers — not an error, just a silently incorrect -1.

This leads to a trap worth knowing: if your data isn't already sorted, sorting it costs O(n log n), which is more than the O(n) of just scanning once. Sorting to enable a single binary search is a net loss. Sorting once to enable thousands of searches is a big win.

---

Complexity Analysis

• Time (worst/average): O(log n) — the search space halves each iteration, so it takes log₂(n) steps to reach one element.

• Time (best): O(1) — the target happens to be the first middle element you check.

• Space (iterative): O(1) — just two pointers.

• Space (recursive): O(log n) — one stack frame per level.

---

The Two Bugs Everyone Writes

Infinite loop. If you write low = mid instead of low = mid + 1, and mid happens to equal low, the range stops shrinking and the loop never ends. Always move past the midpoint you just rejected.

Off-by-one in the condition. Using while (low < high) instead of while (low <= high) skips the final single-element check, so you miss targets sitting at the last position. These two must be consistent with each other:

// Consistent pair A (what we used above):
while (low <= high)  with  high = arr.length - 1

// Consistent pair B (half-open range):
while (low < high)   with  high = arr.length

Pick one convention and stick with it. Mixing them is where the bugs come from.

---

Common Interview Variations

Find the first occurrence of a repeated value. Don't stop at the first match — record it and keep searching left:

function findFirst(arr, target) {
  let low = 0, high = arr.length - 1, result = -1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (arr[mid] === target) {
      result = mid;      // candidate found
      high = mid - 1;    // but keep looking further left
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

findFirst([1, 2, 2, 2, 3, 4], 2); // 1

Swap high = mid - 1 for low = mid + 1 in the match branch and you get the last occurrence instead.

Search in a rotated sorted array. Given [13, 18, 19, 1, 3, 4, 6], one half is always still sorted — identify which, then decide whether the target lies inside it.

Binary search on the answer. The most powerful variation. When you can ask "is X good enough?" and the answer is monotonic (false, false, false, true, true), you can binary search the answer space itself — even with no array involved. Problems like "minimum capacity to ship packages in D days" are solved this way.

---

Where You'll Meet It in Real Code

• Database indexes. B-tree indexes are a generalisation of the same halving idea — it's why an indexed WHERE lookup is fast and a full table scan isn't.

• Git bisect. git bisect is binary search over your commit history to find the commit that introduced a bug.

• Autocomplete and dictionaries. Finding the range of entries sharing a prefix in a sorted word list.

• Version resolution. Package managers binary search sorted version lists to resolve constraints.

---

Practice Problems

Work through these in order — each adds one twist to the base algorithm:

1. Search Insert Position (LeetCode 35) — return where the target would go

2. First and Last Position in Sorted Array (LeetCode 34) — the variation above

3. Search in Rotated Sorted Array (LeetCode 33)

4. Koko Eating Bananas (LeetCode 875) — binary search on the answer

---

Conclusion

Binary search turns an O(n) problem into an O(log n) one just by using the fact that the data is sorted. Get the loop condition and the pointer updates consistent, use low + (high - low) / 2 out of habit, and trace one example by hand until the shrinking range feels obvious.

Once this pattern clicks, you'll start spotting places to apply it well beyond plain array searching — especially the "search on the answer" variation, which turns a surprising number of optimisation problems into a few lines of code.

For the complexity notation used throughout this post, see Big O Notation Explained. Next in this series: Sorting Algorithms Explained.

Image: AlwaysAngry / Wikimedia Commons (CC BY-SA 4.0)