Petr

Posted on Sep 25

Hard to Memorize, Easy to Understand: Binary Search

#algorithms #learning #leetcode #beginners

Why Another Article About Binary Search?

As a rule, tutorials boil down to showing a single "correct" solution. You can try to memorize such solutions, but they are quickly forgotten and don't help you truly understand the algorithm.

I'm intrigued by a question: is an explanation possible that allows you to understand the logic itself, not just memorize formulas? And if such an explanation exists, will it provide the ability to solve similar problems—or even help you become a better programmer?

Let me be clear upfront: we won't dwell on trivial checks, like an empty array or invalid parameters. The focus of this article is on the essence of the algorithm.

In this article, we won't just look at ready-made code. Instead, we will:

Break down the key idea of the algorithm with a simple example.
Focus on an edge case where most people make a mistake.
Compare two implementation approaches—with a closed and a half-open interval.
See how small changes in the code allow us to solve a whole class of problems.

1. Introduction

To make the following explanation concrete, I will use a specific array, sorted in non-decreasing order, and a target value in the examples:

const arr = [2, 7, 8, 11, 15, 29, 31];
const target = 30;

2. The Key Idea

I won't go into too much detail on the basic logic of binary search. Almost every introductory article demonstrates it with beautiful visualizations. In this article, I want to emphasize a key edge case, the analysis of which, I believe, will allow you to understand the implementation, not just memorize it.

We have a non-decreasingly sorted array arr and a target value target.
We define two pointers: left and right. We'll set left to the far-left index and right to the far-right index:
```
let left = 0;
let right = arr.length - 1;
```

We calculate mid—the index that is in the middle between left and right:

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

Once we have the mid index, we can take the corresponding value from the array and compare it with target. Because the array is sorted, we can immediately tell if target is to the left or right of arr[mid]:

if (target === arr[mid]) {
  return mid; // found target, return the index
} else if (target > arr[mid]) {
  // target is greater than arr[mid] — so it's in the right half
} else {
  // target is less than arr[mid] — so it's in the left half
}

We have determined which half of the array the desired element is in, which means we can discard the other half and continue the search only in the remaining part. Thus, in one operation, we reduce the search range by half.

In binary search, we repeat this sequence of actions, reducing the range at each step, until we find the target value or until the left and right pointers cross—which means the target does not exist in the array.

3. The Classic Solution

There are several ways to implement binary search. We will now look at the classic solution with a closed interval, which is most commonly found in articles and tutorials.

This solution, in my opinion, is the most understandable for those who are just getting acquainted with binary search: a simplified calculation of mid, and when narrowing the range—subtract one for right, add one for left.

export function binarySearchClosedInterval(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

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

As you can see, this implementation fully corresponds to the logic I described at the beginning of the article. But this is where the details emerge that are much better to understand than to memorize.

4. The Key Edge Case

I argue that understanding the edge case we will discuss in this section will simplify writing binary search logic for you in any task and will allow you to not memorize the details where 90% of programmers make mistakes.

Let's return to the basic logic of binary search:

Create left and right pointers.
Calculate the middle index mid.
Compare the target value with arr[mid]. If target is greater—take the right half of the array, if less—the left half.

The critical edge case for understanding arises in steps 2 and 3. It lies in the fact that for two adjacent indices, the formula for calculating mid returns the smaller of them, and without an "auxiliary shift," the pointers will not be able to cross.

For example: suppose left = 5 and right = 6. Then mid = Math.floor((5 + 6) / 2) will yield 5.

A small note: there are several formulas for calculating mid, but this edge case is relevant for all of them. (I will talk about the "advanced" formula separately—for now, we continue with the example from the beginning of the article).

Let's see in detail how binary search breaks if we don't make an "auxiliary shift" when processing adjacent indices. To show this, let's replace the correct code with an incorrect one:

CORRECT CODE

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

INCORRECT CODE

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

Now let's substitute the incorrect code into our binary search function and see what happens:

export function binarySearchWithError(
  arr = [2, 7, 8, 11, 15, 29, 31],
  target = 30
) {
  let left = 5;
  let right = 6;

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

    if (target === arr[mid]) { // false
      return mid;
    } else if (target < arr[mid]) {
      right = mid;
    } else { // true
      left = mid; // 5
    }
  }
  return -1;
}

On the next iteration, the pointers will remain the same: [left, right] = [5, 6]. mid will again be 5, and the loop will never end—it has become infinite.

Note: it doesn't matter which of the boundaries doesn't move—even if left and right are equal at some point (e.g., [5, 5]), but mid is still 5, the situation will remain a dead end—and again an infinite loop.

This error is solved by adding an auxiliary shift of one:

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

Conclusions

Binary search must narrow down on every iteration. This works until the search comes down to comparing two adjacent indices.

In this edge case, it is important to understand that mid will be equal to left, and you cannot reassign left = mid or right = mid—otherwise, the range will not change, and the loop will become infinite.

You can look at it differently: when we shift the boundaries by one, we simply exclude the mid index, which has already been checked, from the range. There is no reason to keep it in the next iteration.

5. Closed and Half-Open Intervals

Understanding how the implementation of binary search depends on the type of interval—closed or half-open—helps to deal with the edge case of an infinite loop with adjacent indices, and generally never get confused in the implementation details again.

Before we go further, I want to fix two thoughts:

The topic of intervals is broader than binary search. In this article, I do not aim to tell the theory or history of intervals—I want to give practical information in the context of binary search. If you are interested in the topic more deeply, I recommend starting with Edsger Dijkstra's article "Why numbering should start at zero."
There is a separate term—off-by-one error. It describes typical errors in loops when the number of iterations is one more or one less than necessary. The infinite loop we discussed above is a classic example of an off-by-one error. And I dare to assume that one of its main causes is the unconscious choice of the interval type.
https://en.wikipedia.org/wiki/Off-by-one_error

5.1. Simple Loop with a Closed Interval

A range determines which index values will participate in the iteration. In the case of a closed interval:

for (let i = 0; i <= arr.length - 1; i++) {}

Features:

The start (0) and end (arr.length - 1) boundaries are inclusive.
The condition i <= ... is used to not miss the last element.
The "calling card" is the need to subtract 1 from the array length when setting the right boundary. It is this -1 that is often considered a source of potential errors.

5.2. Simple Loop with a Half-Open Interval

This is a more modern and idiomatic approach, especially in JavaScript (think of .slice(start, end)). In a half-open interval:

for (let i = 0; i < arr.length; i++) {}

The starting point (0) is inclusive, and the ending point (arr.length) is exclusive.
Therefore, in the loop condition, we use the strict comparison operator <. The loop will stop as soon as the iterator reaches the final, non-inclusive point.
The "calling card" of this approach is the use of the "clean" array length (arr.length) as the endpoint. There are no -1s here, which makes the code cleaner and more intuitive.

5.3. Binary Search with a Half-Open Interval

Now let's look at binary search implemented using a half-open interval:

function binarySearchHalfOpenInterval(arr, target) {
  let left = 0;
  let right = arr.length;

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

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

  if (left === arr.length || arr[left] !== target) return -1;
  else return left;
}

In accordance with the elementary example of a half-open loop, we see that in this implementation of binary search, the starting point of the interval is always inclusive, and the ending point is exclusive.

In practice, this means that we do not need to remember to subtract one when updating the right boundary. The rightmost index is by default unreachable—it is excluded from the range by the loop condition while (left < right).

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

Another important feature of this implementation is that we do not directly compare arr[mid] with target. We return left, which ultimately, thanks to the condition left = mid + 1, will be the index of the element to the left of which are all values strictly less than target. Consequently, the value at the index left itself is the first element equal to or greater than target.

This feature makes the implementation universal: it immediately solves several popular problems based on binary search. For example, the task findLeftBoundary / Find First Occurrence / lower_bound.

function findLeftBoundry(arr, target) {
  let left = 0;
  let right = arr.length;

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

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

  if (left === arr.length) return -1;
  else return left;
}

And if you change the condition a bit and return left - 1, you get the solution to the findRightBoundary / Find Last Occurrence / upper_bound problem:

function findRightBoundry(arr, target) {
  let left = 0;
  let right = arr.length;

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

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

  return left - 1;
}

5.4. Binary Search with a Closed Interval (Revisited)

The classic solution for searching with a half-open interval differs from the classic implementation with a closed interval. Interestingly, and you may have noticed, the difference is not only in the intervals themselves.

In the implementation with a half-open interval, the search continues until all values strictly less than target are on the left:

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

And in the classic (and most popular!) implementation with a closed interval, the comparison arr[mid] === target is performed immediately, and if they match, the index is returned immediately:

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

Consequently, one of the final thoughts of this article is that the implementation of binary search with a closed and half-open interval differs not only formally—by intervals—but also in the approach to the search logic itself.

We can well write an implementation with a closed interval that will work on the principle of the half-open version—without an immediate return, simply by narrowing the range to the desired point.

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

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

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

  if (left < arr.length && arr[left] === target) {
    return left;
  }

  return -1;
}

6. The Overflow Bug

Calculating mid seems like simple arithmetic, but there is a nuance: the expression (left + right) / 2 can overflow in languages with a fixed integer type. As a result, mid will be incorrect, and the algorithm will behave unpredictably. To avoid this, a safer form is used:

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

Why this is safe:

right - left never exceeds the length of the range; as long as right >= left, the difference will not overflow the type.
Then we add half of this difference to left—the result always remains within the allowable indices.

DEV Community