How does binary search work? Implement it in C#, explain its preconditions and edge cases, and compare it with linear search and hash lookup. When would you use each in a .NET application?

1. A correct binary search

Binary search is famous for off-by-one bugs. Use a half-open or closed interval consistently.

// Closed interval [lo, hi]. Returns index, or ~insertionPoint when not found (same contract as Array.BinarySearch).
static int BinarySearch(ReadOnlySpan<int> a, int target)
{
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + ((hi - lo) >> 1);   // avoids int overflow of (lo + hi)
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return ~lo;                            // lo is where target would be inserted
}

Why lo + (hi - lo) / 2? With arrays near int.MaxValue elements, lo + hi can overflow to a negative number. This exact bug sat in the JDK's binary search for about nine years.

2. The insertion-point contract

Array.BinarySearch returns a negative number when the item is missing: the bitwise complement of the index where it would go.

int[] a = { 10, 20, 30 };
int i = Array.BinarySearch(a, 25);   // returns ~2 == -3
int insertAt = ~i;                   // 2

This makes "insert in sorted order" and "find nearest" cheap.

3. Lower bound and upper bound

Most real problems are not "is x here?" but "where does x start?":

index:   0  1  2  3  4  5
value:  [1, 3, 3, 3, 7, 9]
lowerBound(3) = 1   (first >= 3)
upperBound(3) = 4   (first > 3)
count of 3s = upper - lower = 3

static int LowerBound(ReadOnlySpan<int> a, int x)
{
    int lo = 0, hi = a.Length;           // half-open [lo, hi)
    while (lo < hi)
    {
        int mid = lo + ((hi - lo) >> 1);
        if (a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Array.BinarySearch returns some matching index when duplicates exist, not necessarily the first. Use a lower bound when you need the first.

4. Binary search on the answer

Binary search works on any monotonic predicate, not just arrays. "What is the smallest batch size that finishes within the time limit?" If ok(size) is false then true as size grows, binary-search the size. The same trick finds the first bad build in a range (that is what git bisect does).

5. Preconditions that bite in .NET

Always pass the same comparer to Sort and BinarySearch.

6. Linear search is not always slow

Modern CPUs prefetch sequential memory and .NET vectorises IndexOf for primitives with Vector128/256/512. Binary search jumps around memory and mispredicts branches. For arrays smaller than roughly 32–64 ints, a linear scan often wins. Measure before "optimising" a tiny list.

7. Try it yourself

var data = Enumerable.Range(0, 1_000_000).Select(i => i * 2).ToArray(); // sorted even numbers
Console.WriteLine(Array.BinarySearch(data, 500_000));   // 250000
int miss = Array.BinarySearch(data, 7);
Console.WriteLine($"{miss} -> insert at {~miss}");     // -5 -> insert at 4
Console.WriteLine(LowerBound(data, 7));                  // 4

static int LowerBound(ReadOnlySpan<int> a, int x)
{
    int lo = 0, hi = a.Length;
    while (lo < hi) { int mid = lo + ((hi - lo) >> 1); if (a[mid] < x) lo = mid + 1; else hi = mid; }
    return lo;
}

Then break it on purpose: shuffle data and see BinarySearch return nonsense without throwing.

// Effective-dated lookup: last tariff whose From <= date
public sealed class TariffTable
{
    private readonly Tariff[] _byFrom;      // sorted once
    private readonly DateOnly[] _from;

    public TariffTable(IEnumerable<Tariff> tariffs)
    {
        _byFrom = tariffs.OrderBy(t => t.From).ToArray();
        _from = Array.ConvertAll(_byFrom, t => t.From);
    }

    public Tariff? For(DateOnly date)
    {
        int i = Array.BinarySearch(_from, date);
        if (i < 0) i = ~i - 1;              // insertion point minus one = last From <= date
        return i >= 0 ? _byFrom[i] : null;
    }
}

// Exact lookups: build once, O(1) each
var blocked = new[] { "[email protected]", "[email protected]" }.ToFrozenSet(StringComparer.OrdinalIgnoreCase);
bool isBlocked = blocked.Contains(email);

// Searching for any of several characters: SearchValues (vectorised)
private static readonly SearchValues<char> Separators = SearchValues.Create(",;|\t");
int pos = line.AsSpan().IndexOfAny(Separators);

// Same comparer for sort and search
var names = new List<string> { "bob", "Alice", "carol" };
names.Sort(StringComparer.OrdinalIgnoreCase);
int idx = names.BinarySearch("ALICE", StringComparer.OrdinalIgnoreCase); // 0