Binary Search Tool

This JS toy allows you to play around with different variants of binary search.

Notes

This tool tries to list all the ways that a binary search over a sorted list can work in Python. Unlike C++, Java, Go, or other languages, this doesn't handle all the variant midpoint calculations. Instead, it focuses on the boundary conditions. Also unlike most other languages, this code tries to find the "insertion" point for a search value, rather than the index of the search element. Other binary search implementations return more complex or more nuanced variants, such as returning negative values in Java, "left" and "right" variants in Python, a "Result" enum in Rust, etc.

Some conditions appear redundant, especially with lo < hi appearing to be the same as hi > lo. These variants are meant to help show the code is correct when overloading the operators with custom implementations; it may be inconvenient to convert a < implementation into a >.

While the generated code shows how to search a list of integers, the code should also work with other types, such as floats, strings, ranges, etc. This code assumes the range of values is totally ordered.

Several languages have a "spaceship" operator, which can return the full range of comparison operations. This code currently doesn't use equality, since it isn't strictly necessary, and instead relies solely on the inequality operators.

Consider the problem of trying to sort Calendar events:

@dataclass
class Event:
    start: int
    end: int

    def __lt__(self, other):
        return self.start < other.start

Suppose we have a binary search implementation that used <= instead of <, to our dismay. This object doesn't provide an equality method. We could implement it, but that may be impractical to copy and maintain that code. We could simulate it so that it works with the binary search function:

@dataclass
class Event:
    start: int
    end: int

    def __lt__(self, other):
        return self.start < other.start

    def __lte__(self, other):
        return self < other or (not other < self)

The modified code is less easy to read. Really, it would be better to modify our binary search to use the correct comparison function.

Non-Mobile view: bsearch.html