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

</aside>

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

Discrete intervals

<aside> ☝ A discrete interval should always be in the form [left, right)

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

</aside>

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

<aside> ☝ 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.

</aside>

The middle point

<aside> ☝ 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

</aside>

The main loop of binary search

<aside> ☝ 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

</aside>

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

<aside> ☝ 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:

</aside>