Binary search done right: introduction

💡

This note is dedicated to a fast, clean and safe coding approach to discrete binary search problem.

All the code snippets are given in Python, but the principle can be applied to any language of your choice.

Discrete intervals Discrete binary search Initial values The middle point The main loop of binary search Choosing the boundaries of the halves Example: finding a number in a sorted array Implementation

Discrete intervals

☝

A discrete interval should always be in the form [left, right)

[left, right) := [left, left+1, ..., right-1]

Some people use intervals of the form [left, right], which includes the right endpoint into the interval, but it leads to messing around with adding or subtracting 1. We will see more advantages of half-open intervals below in this note.

Discrete binary search

We use discrete binary search to find the maximal interval of the form [0, R) satisfying some property. The problem is that there is always a mess with adding or subtracting 1, because the binary search is, well, discrete.

Initial values

☝

Recall that we agreed to always use the [left, right) type intervals. We need to set the boundaries of the binary search first. For example:

left = 0
right = len(array)

In this case, we need to guarantee that the left endpoint satisfies the property, and the right endpoint doesn’t. The latter is often the case, since the index right is out of boundaries of the array. In some cases we would need to set left = -1.

The middle point

☝

Even if the indices left and right are out of the array boundaries, we might actually never get to access these indices. In fact, we only need to access the values of the intermediate middle values: the centre is calculated at the beginning of the loop and it is the only index that is used.

m = left + (right - left) // 2

This part of assignment is historically used in C++ because int type is bounded by some finite value, so we can avoid overfill. This is not really an issue in Python but can be kept for backward compatibility.

Another reason to prefer the above writing to m = (left + right) // 2 is because of using pointers. For most pointers, the difference of two pointers is of type int, and an addition between a pointer and an integer is well-defined. On the contrary, two pointers cannot be summed up.

I don’t really see any use cases for choosing pointers instead of integers, because if a pointer is not random access, then taking a difference would take a linear time instead of O(1). This would make binary search slower than plain linear search.

Note that if left and right are adjacent, then the midpoint always falls on the left, regardless of parity:

left + (right - left) // 2 == left

The main loop of binary search

☝

The right side of the segment is always guaranteed to not satisfy the property, and the left is guaranteed to satisfy it. Therefore, the difference right - left will always be at least 1. This assumption allows us to terminate the loop only if this difference achieves the value 1.

while right - left > 1:
    mid = left + (right - left) // 2
    if property(mid):
        ... # choose the right half
    else:
        ... # choose the left half

At the end of the loop, right == left + 1. The target segment is [left,right) and contains exactly one element left.

Choosing the boundaries of the halves

☝

When choosing the right half, we need the interval [mid, right), because the property is satisfied at the left of this interval, at point mid. When choosing the left half, we are guaranteed that the property does not hold for mid, and so this index can be indeed chosen as the right endpoint: [left, mid), because the interval now does not include this value. No further adding or subtracting of 1 is required! Here is how the code finally looks like:

left = 0
right = len(array)
while right > left:
    mid = left + (right - left) // 2
    if property(mid):
        left = mid # choose the right half
    else:
        right = mid # choose the left half

## at the end of the loop, right == left + 1
## The desired value is on the left.

To sum up, this innocent-looking pattern can be used in various situations, as long as you reflect upon the structure of a half-open interval, clearly formulate the property that you are searching for, and correctly identify the initial left and right bounds for the binary search, based on the property that you formulated.

Example: finding a number in a sorted array

Here is the most classical application of the binary search - let us use this example to see the best way to code it quickly and safely.

💡

Given a discrete sorted array arr and a number t, find the maximal index idx such that arr[idx] <= t. (See examples below)

Note that the number t may be a priori less than the minimal index of the array or greater than the maximal index.

Examples.

>>> arr = [10, 20, 30]
>>> find(arr, 5)
-1
>>> find(arr, 10)
0
>>> find(arr, 15)
0
>>> find(arr, 35)
2

The real line can be partitioned into four intervals according to the definition of the initial array:

The intervals have indices -1, 0, 1, 2, and the goal is to find the index of the interval for a given input number.

Implementation

This part is really important: We need to guarantee that initially, the left boundary satisfies the property and the right one doesn’t. Sometimes you will be tempted to violate this property, but you should not, because this introduces tons of code duplication and case-checking. Really, don’t skip this part. It is always better to spend extra time and explicitly formulate the property and carefully choose the left and the right boundaries. Then, the rest of the code will follow a simple template.

In our example, the property is defined simply as arr[i] <= t.

Assume by extension that arr[-1] = -infty and arr[len(arr)]=+infty.

We don’t actually have to access these infinite values, nor mimic the infinities by using some python datatypes. This is more of a mathematical assumption.
We could, however, use float(”inf”) which perfectly mimics a mathematical infinity if necessary.
If you want to avoid using infinite values and/or dislike this approach for some reason, this leads to additional checks. They could be implemented in a separate function for convenience.

Set left = -1 and right = len(arr). Don’t worry that these two indices are out of boundaries, they will never be accessed! The intermediate value mid will always be between 0 and len(arr)-1.

Check for the corner cases, just in case! When the array is empty, we have left = -1, and right = 0. Therefore the loop is never executed since right-left is 1 and the function returns find(elem, arr) = -1.

Here is the final implementation, leading to a tight and simple code.

def find(elem, arr):
    left = -1
    right = len(arr)
    while right - left > 1:
        mid = left + (right - left) // 2
        if arr[mid] <= t:  ## put any property you want here
            left = mid
        else:
            right = mid
    return left

Next post: Binary search done right: finding the median of a union in logarithmic time