Closed vs Half-Open Binary Search: Eliminating Off-by-One Infinite Loops

Why Binary Search Bugs Persisted for 60 Years

Jon Bentley famously reported in Programming Pearls that over $90\%$ of professional programmers failed to write a bug-free binary search in an hour, and Joshua Bloch revealed in 2006 that Java's Arrays.binarySearch had contained a signed integer overflow bug (int mid = (low + high) / 2; overflowing when low + high >= 2^31) for nearly a decade. Every binary search bug stems from one of two root causes:

1. Signed Midpoint Overflow: Writing (lo + hi) / 2 instead of lo + (hi - lo) / 2 or C++20's overflow-free std::midpoint(lo, hi).
2. 2-Element Infinite Loops (lo = mid with Floor Rounding): When $hi = lo + 1$, integer floor division sets $mid = \lfloor(lo + hi)/2\rfloor = lo$. If the loop body executes lo = mid without advancing past $mid$, the interval $[lo, hi]$ never shrinks and loops forever!

Production C++20 Implementation: Half-Open lower_bound, upper_bound & Branchless Search

#include <bit>
#include <concepts>
#include <cstddef>
#include <numeric>

// 1. Canonical Half-Open [lo, hi) lower_bound: First index i in [0, n] with !(a[i] < target)
template <std::totally_ordered T>
constexpr std::size_t lower_bound_half_open(const T* a, std::size_t n, const T& target) noexcept {
    std::size_t lo = 0;
    std::size_t hi = n; // Half-open [0, n): n is the "not found / past-the-end" sentinel
    while (lo < hi) {
        const std::size_t mid = std::midpoint(lo, hi); // Overflow-safe lo + (hi - lo) / 2
        if (a[mid] < target) {
            lo = mid + 1; // mid is strictly False; advance past mid
        } else {
            hi = mid;     // mid is True (a[mid] >= target); keep mid in candidate range
        }
    }
    return lo;
}

// 2. Canonical Half-Open [lo, hi) upper_bound: First index i in [0, n] with target < a[i]
template <std::totally_ordered T>
constexpr std::size_t upper_bound_half_open(const T* a, std::size_t n, const T& target) noexcept {
    std::size_t lo = 0;
    std::size_t hi = n;
    while (lo < hi) {
        const std::size_t mid = std::midpoint(lo, hi);
        if (!(target < a[mid])) { // a[mid] <= target (False)
            lo = mid + 1;
        } else {                  // a[mid] > target  (True)
            hi = mid;
        }
    }
    return lo;
}

// 3. Branchless CMOV Lower Bound (Paul-Virak Khuong & Pat Morin style)
template <std::totally_ordered T>
constexpr std::size_t lower_bound_branchless(const T* a, std::size_t n, const T& target) noexcept {
    if (n == 0) return 0;
    const T* base = a;
    std::size_t len = n;
    while (len > 1) {
        const std::size_t half = len >> 1;
        // Compiles to a single CMP + CMOV with zero branch mispredictions!
        base += (base[half - 1] < target) ? half : 0;
        len -= half;
    }
    return static_cast<std::size_t>(base - a) + ((*base < target) ? 1U : 0U);
}