This note is dedicated to fast, clean and safe coding of discrete binary search
Discrete intervals
A discrete interval should always be in the form [l, r)
Discrete binary search
We use discrete binary search to find the maximal interval satisfying some properties. The problem is that there is always a mess with adding or subtracting 1. We often are left with two endpoints which are different and need to do separate check on them which leads to code duplication. At the end of the while loop we need to have l=r . How do we achieve it?
Initial values
Since we sweared to always use the [l, r) type intervals, we can confidently set the borders of the binary search:
left = 0
right = len(array)
Copy
Python
Now, it is guaranteed that left endpoint satisfies the property, and the right endpoint doesn’t, since the index right is out of boundaries of the array.
The middle point
We only need to access the values of the middle because we know that left is in the target set and right isn’t.
m = left + (right - left) // 2
Copy
Python
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. The only case when the latter scenario is applicable is when the left and right boundaries are integers and not pointers. 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).
Note that if left and right are adjacent, then the midpoint falls on the left:
left + (right - left) // 2 == left
Copy
Python
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, right-left will always be at least 1.
while right - left > 1:
mid = left + (right - left) // 2
if property(mid):
... # choose the right half
else:
... # choose the left half
Copy
Python
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). 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). 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.
Copy
Python
Example: finding a number in the array
Given a discrete sorted array arr and a number t, find the maximal index idx such that
arr[idx] <= t. Note that the number t may be apriori less than the minimal element of the array or greater than the maximal one.
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:
Implementation
This part is really important: We need to guarantee that 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 and case-checking. It is always better to explicitly formulate the property and appropriately choose the left and the right boundaries. Consequently, the rest of the code follows a simple template.
In our example, the property is defined as arr[i] <= t.
Assume by extension that arr[-1] = -oo and arr[len(arr)]=+oo. We don’t actually have to access these values, nor mimic the infinities by using some python datatypes. This is more of a mathematical assumption.
Set left = -1 and right = len(arr). Don’t worry, these indices will never be accessed!
Check for the corner cases. When the array is empty, we have left = -1, and right = 0. Therefore the loop is never executed and we have find(elem, arr) = -1.
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
Copy
Python