Binary Search in Depth: Lower Bound, Off-by-One and Binary Search on the Answer

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests.

Guess First

Bookstore's price archive holds 1,000,000 sorted prices. When looking for a price with binary search, how many comparisons are made in the worst case: 1,000, 100, 20?

Second question, from a code review: the method below looks for the index of the last element less than or equal to the target in a sorted array. What happens when you look for 20 in the array [10, 20]?

int lo = 0, hi = sorted.Length - 1;
while (lo < hi)
{
    int mid = lo + (hi - lo) / 2;
    if (sorted[mid] <= target) lo = mid;
    else hi = mid - 1;
}
return lo;

Writing Binary Search with an Invariant

As an idea, binary search is very simple: look at the middle element of a sorted array; if the target is smaller, continue in the left half, if larger, in the right half. The range halves at every step; with 1,000,000 elements, at most log₂(1,000,000) ≈ 20 steps. The answer to the first question is 20. But as Jon Bentley describes in his book Programming Pearls, most professional programmers cannot write a bug-free binary search on the first try. Almost all the bugs are at the boundaries: is hi included or not, does mid stay in range on the next step, when does the loop end?

The way to avoid these bugs is to write the code against an invariant, a sentence that stays true at every step. All binary searches in this post use a half-open range: the search space is [lo, hi), lo included, hi excluded. Initially hi = Length, and the loop ends when the range is empty (lo == hi).

namespace Algorithms.Searching;

public static class BinarySearch
{
    // invariant: if the target exists, it is inside [lo, hi). The range shrinks every step.
    public static int IndexOf<T>(ReadOnlySpan<T> sorted, T target, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        int lo = 0, hi = sorted.Length;
        while (lo < hi)
        {
            int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 can overflow when both are large
            int cmp = comparer.Compare(sorted[mid], target);
            if (cmp == 0) return mid;
            if (cmp < 0) lo = mid + 1;
            else hi = mid;
        }
        return -1;
    }
}

You can check every branch against the invariant. If sorted[mid] is smaller than the target, the target is to the right of mid; lo = mid + 1 leaves mid out too. If it is larger, the target is to the left of mid; since hi is excluded, hi = mid already leaves mid out. In both branches the range shrinks by at least one element, so the loop always ends.

Writing mid = lo + (hi - lo) / 2 has a story behind it. (lo + hi) / 2 is mathematically the same, but if lo and hi are both greater than 2³⁰ their sum exceeds the limit of int, becomes negative, and the array is accessed with a negative index. Joshua Bloch announced this bug, which had sat unnoticed in Java's Arrays.binarySearch for nine years, in his 2006 post "Nearly All Binary Searches and Mergesorts are Broken". Since a .NET array can have more than 2³⁰ elements, this is not a theoretical risk.

Lower Bound and Upper Bound

Finding an exact match is the least useful form of binary search. If the price list has three books at 20 TL, IndexOf may return any of them. The questions really asked in production are: "where is the first book not cheaper than 20 TL?" (lower bound) and "where is the first book more expensive than 20 TL?" (upper bound). Both always give an answer; if the target is not there, the answer is where the target could be inserted without breaking the order.

// first index whose item is >= target (insert position); sorted.Length if none
public static int LowerBound<T>(ReadOnlySpan<T> sorted, T target, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    int lo = 0, hi = sorted.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (comparer.Compare(sorted[mid], target) < 0) lo = mid + 1; // mid is too small: answer is right of it
        else hi = mid;                                                  // mid may be the answer: keep it
    }
    return lo;
}

// first index whose item is > target
public static int UpperBound<T>(ReadOnlySpan<T> sorted, T target, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    int lo = 0, hi = sorted.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (comparer.Compare(sorted[mid], target) <= 0) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

public static int CountOf<T>(ReadOnlySpan<T> sorted, T target) =>
    UpperBound(sorted, target) - LowerBound(sorted, target);

Lower bound's invariant is slightly different: "the answer is inside [lo, hi]", and when the loop ends lo == hi is the answer itself. If sorted[mid] >= target, mid may be the answer; hi = mid keeps it. The only difference between the two methods is < versus <=: upper bound puts equal elements on the "smaller" side too. The difference between them is how many times the target occurs; in a sorted array "how many 20 TL books are there?" is answered with two binary searches in O(log n).

private static readonly int[] Prices = [10, 20, 20, 20, 35, 50, 80];

[Theory]
[InlineData(20, 1, 4)]
[InlineData(5, 0, 0)]
[InlineData(21, 4, 4)]
[InlineData(100, 7, 7)]
public void LowerUpperBound_ReturnBoundaries(int target, int lower, int upper)
{
    Assert.Equal(lower, BinarySearch.LowerBound<int>(Prices, target));
    Assert.Equal(upper, BinarySearch.UpperBound<int>(Prices, target));
}

[Fact]
public void LowerBound_MatchesLinearScan_OnRandomData()
{
    Random random = new(21);
    for (int round = 0; round < 200; round++)
    {
        int[] sorted = [.. Enumerable.Range(0, random.Next(0, 50)).Select(_ => random.Next(0, 30)).Order()];
        int target = random.Next(-2, 33);
        int expected = Array.FindIndex(sorted, x => x >= target);
        if (expected < 0) expected = sorted.Length;

        Assert.Equal(expected, BinarySearch.LowerBound<int>(sorted, target));
    }
}

The second test is the safest way to test a binary search: ask the same question with a linear scan as well and check that both answers agree on 200 random arrays. Edge cases such as an empty array, all values equal, or a target smaller or larger than every value come up on their own in the random generation.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.BinarySearchTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (605ms)

Test run summary: Passed!
  total: 17
  failed: 0
  succeeded: 17

The .NET Counterpart: Array.BinarySearch and ~index

Array.BinarySearch, List<T>.BinarySearch and MemoryExtensions.BinarySearch in the BCL (Base Class Library) combine lower bound and exact match in a single return value. If found, they return the index. If not found, in Microsoft Learn's definition they return the bitwise complement of the index of the first element larger than the target, that is ~index. The result is always negative, and flipping it back with ~ gives the insert position:

[Fact]
public void ArrayBinarySearch_Missing_ReturnsComplementOfInsertPosition()
{
    int index = Array.BinarySearch(Prices, 40);

    Assert.Equal(-6, index);
    Assert.Equal(5, ~index);
    Assert.Equal(5, BinarySearch.LowerBound<int>(Prices, 40));
}

[Fact]
public void ListBinarySearch_InsertKeepsSorted()
{
    List<int> prices = [10, 20, 35, 50];
    foreach (int price in new[] { 40, 5, 99, 20 })
    {
        int index = prices.BinarySearch(price);
        prices.Insert(index < 0 ? ~index : index, price);
    }

    Assert.Equal([5, 10, 20, 20, 35, 40, 50, 99], prices);
}

~5 is -6. Why the complement and not -1? Because inserting at position 0 is also a valid answer and there is no int called -0; ~0 = -1 means "not found, insert at the front". The second test shows the idiomatic way to keep a list sorted with BinarySearch + Insert. The search is O(log n), but Insert is O(n) because of the shifting we saw in the series' second post. For a sorted collection with very frequent inserts, SortedSet or SortedDictionary fits better; the choice is covered in the C# Collections series post "Sorted Collections in C#: SortedList, SortedDictionary, SortedSet and IComparer".

One more detail: if the target occurs more than once, which one Array.BinarySearch returns is not guaranteed. According to the documentation it returns only one of the occurrences, and which one is not specified. If you need the first or the last, write your own lower/upper bound.

Binary Search on the Answer

The most powerful use of binary search is not searching an array but searching a range of answers. Bookstore's warehouse ships a list of parcels in order with a single truck every day; parcels are loaded in order, the truck leaves when it is full, and the rest wait for the next day. What is the minimum capacity of the truck to rent so that all parcels are gone in 5 days?

There is no formula that computes the capacity directly. But the reverse is easy: given a capacity, you can compute the number of days needed in a single pass. And that answer is monotonic: as the capacity grows, the number of days never grows. The answer to "does this capacity finish in 5 days?" is always no for small capacities and always yes past some threshold. You can find that threshold with binary search:

// smallest x in [lo, hi] with predicate(x) == true; predicate must be false...false true...true
public static long FirstTrue(long lo, long hi, Func<long, bool> predicate)
{
    while (lo < hi)
    {
        long mid = lo + (hi - lo) / 2;
        if (predicate(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

public static class Shipping
{
    // smallest truck capacity that ships all parcels, in order, within "days" days
    public static long MinCapacity(int[] parcelWeights, int days) =>
        BinarySearch.FirstTrue(parcelWeights.Max(), parcelWeights.Sum(), capacity => DaysNeeded(parcelWeights, capacity) <= days);

    public static int DaysNeeded(int[] parcelWeights, long capacity)
    {
        int daysUsed = 1;
        long load = 0;
        foreach (int weight in parcelWeights)
        {
            if (load + weight > capacity)
            {
                daysUsed++;
                load = 0;
            }
            load += weight;
        }
        return daysUsed;
    }
}

[Fact]
public void MinCapacity_ShipsWithinDays()
{
    int[] parcels = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    long capacity = Shipping.MinCapacity(parcels, days: 5);

    Assert.Equal(15, capacity);
    Assert.Equal(5, Shipping.DaysNeeded(parcels, 15));
    Assert.Equal(6, Shipping.DaysNeeded(parcels, 14));
}

The bounds of the search range also come from the problem itself: the capacity cannot be smaller than the heaviest parcel (that parcel would never leave) and need not be larger than the total weight (everything leaves in one day). The second and third asserts in the test prove that the answer really is the threshold: 15 is enough for 5 days, 14 needs 6 days. The search is O(log(total) · n): one pass per candidate capacity, log(total) candidates.

The same template fits a surprising number of problems: the minimum number of servers needed to handle a given load with a given latency, the minimum parallelism for a report batch to finish in an hour, the minimum size of the largest part when splitting a book among N readers. What they all share is a monotonic yes/no question: a condition that turns to yes as something grows and never turns back to no.

Real Life: a Time Range in a Log and git bisect

The binary search you meet most often in production is finding a range in something sorted by time. Bookstore's payment service keeps a log that writes an event every 30 seconds throughout the day; the events between 10:00 and 10:05 are requested:

public sealed record LogEntry(DateTimeOffset Time, string Message);

public static class LogSearch
{
    private static readonly Comparer<LogEntry> ByTime = Comparer<LogEntry>.Create((a, b) => a.Time.CompareTo(b.Time));

    // entries with from <= Time < to, from a log sorted by time
    public static ReadOnlySpan<LogEntry> Between(LogEntry[] sortedLog, DateTimeOffset from, DateTimeOffset to)
    {
        int start = BinarySearch.LowerBound<LogEntry>(sortedLog, new LogEntry(from, ""), ByTime);
        int end = BinarySearch.LowerBound<LogEntry>(sortedLog, new LogEntry(to, ""), ByTime);
        return sortedLog.AsSpan(start, end - start);
    }
}

[Fact]
public void LogSearch_ReturnsHalfOpenRange()
{
    DateTimeOffset t0 = new(2026, 11, 8, 9, 0, 0, TimeSpan.Zero);
    LogEntry[] log = [.. Enumerable.Range(0, 600).Select(i => new LogEntry(t0.AddSeconds(i * 30), $"event {i}"))];

    ReadOnlySpan<LogEntry> window = LogSearch.Between(log, t0.AddMinutes(60), t0.AddMinutes(65));

    Assert.Equal(10, window.Length);
    Assert.Equal("event 120", window[0].Message);
    Assert.Equal("event 129", window[^1].Message);
}

The half-open range makes things easy here too: two lower bounds are enough for [from, to), and consecutive windows ([10:00, 10:05), [10:05, 10:10)) neither overlap nor leave a gap. The result is not a copy but a ReadOnlySpan over the original array; no extra memory. In a database the same job is done with an index on the time column; we will see the B-tree structure of that index in the series' balanced tree post.

git bisect is the same idea, only over commit history instead of a sorted array: "does this commit have the bug?" is monotonic (good, good, ..., bad, bad), and git asks you to test the commit in the middle of the range at each step. In a range of 1,000 commits you find the commit that introduced the bug in 10 steps. Its usage is in the Git series post "Git bisect and git worktree: Finding the Bad Commit and Two Branches at Once".

In Production

Binary search's only precondition is being sorted, and no code checks it. If the code that sorts the array and the code that searches it live in different places, when one changes and the other does not, the search silently starts giving wrong answers. Keep sorted data inside a type that guarantees its order (SortedSet, your own SortedPriceList class), or at least check the order with Debug.Assert in Debug builds.

Sorting and searching must use the same comparer. Searching a list sorted with StringComparer.OrdinalIgnoreCase using the default comparer misses keys that differ in case. In the documentation's words, the array must be sorted according to the given comparer.

Binary search minimizes the number of comparisons, but its memory access is random. In very large arrays each step lands on a different cache line, even a different page. Measure on hot paths with millions of lookups; sometimes a Dictionary, or a smaller index that fits in the cache, is faster.

Common Pitfalls

An infinite loop with lo = mid. The answer to the second opening question: in [10, 20], lo = 0, hi = 1, mid = 0, and since sorted[0] <= 20, lo = mid = 0. Nothing changes; the loop runs forever. The test catches it by putting a step limit on the loop:

// "lo = mid" with the round-down midpoint: when hi == lo + 1, mid == lo and nothing changes
public static int LastAtMost(int[] sorted, int target, int maxSteps)
{
    int lo = 0, hi = sorted.Length - 1, steps = 0;
    while (lo < hi)
    {
        if (++steps > maxSteps) return -999; // stand-in for "this loop never ends"
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] <= target) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

[Fact]
public void BuggyLastAtMost_LoEqualsMid_NeverTerminates()
{
    Assert.Equal(-999, BuggyBinarySearch.LastAtMost([10, 20], 20, maxSteps: 1_000));
}

The rule is simple: if you write lo = mid, mid must round up (lo + (hi - lo + 1) / 2); better still, use a half-open template like the one in this post, where every branch is guaranteed to shrink the range. "Last ≤ target" is really UpperBound(target) - 1.

Searching unsorted data. No exception, only a wrong answer:

[Fact]
public void UnsortedInput_SilentlyMissesExistingItem()
{
    int[] unsorted = [50, 10, 80, 20, 35];

    Assert.True(Array.BinarySearch(unsorted, 35) < 0); // 35 is at index 4
}

35 is in the array, but binary search looks at the middle 80, goes to the left half and never sees it. An array "sorted" with the broken comparer from the series' previous post produces the same result.

Mixing range definitions. Mixing parts of a closed range ([lo, hi], hi = Length - 1, while (lo <= hi)) and a half-open range ([lo, hi), hi = Length, while (lo < hi)) in the same method is the main source of off-by-one bugs. Pick one and use it across the whole code base.

A Small Experiment

★☆☆ Fix BuggyBinarySearch.LastAtMost by rounding mid up, and update the same test to expect the correct answer (index 1). Then do the same job with UpperBound(target) - 1 and compare both versions on random arrays.

★★☆ Bookstore's book club wants to split a 600-page book into chapters and spread it over 7 days; chapters cannot be split and their order does not change. Find the split that minimizes the maximum number of pages read in a day using FirstTrue. How does it differ from MinCapacity?

★★★ Write a method that finds a value in O(log n) in a sorted but rotated array (for example [50, 80, 10, 20, 35], a sorted array cut at one point and swapped around). Hint: at every step one of the two halves is always sorted.

Binary search finds things in log n steps in a sorted array, but inserting into it is O(n). In the next post we move on to the structure that tries to do both searching and inserting in log n: the binary search tree. Insert, find and the three cases of delete, the four kinds of traversal, and building a tree in O(n) from a flat category table in the database.