Binary Search in C#: Beyond Finding an Element

Almost everyone can write binary search over a sorted array. Almost nobody reaches for it when the problem never mentions an array.

That is the gap this part is about. Four of the five patterns here do not search a collection.

Every program below is complete, was run on .NET 10, and its output is pasted from the run.

Pattern 16 — What Array.BinarySearch gives you, and what it does not

The BCL already has it, and its return value on a miss is the most wasted feature in the whole class.

int[] a = [10, 20, 20, 20, 30, 40];

// The BCL search. On a miss it returns the bitwise complement of where the
// value WOULD go — which is the insertion point, not an error.
foreach (int want in new[] { 30, 25, 5, 50 })
{
    int r = Array.BinarySearch(a, want);
    Console.WriteLine(r >= 0
        ? $"BinarySearch({want,2}) = {r,2}   found at index {r}"
        : $"BinarySearch({want,2}) = {r,2}   not found; ~{r} = {~r} is where it would go");
}

// With duplicates, BinarySearch promises nothing about WHICH match you get.
// These two do.
static int LowerBound(int[] a, int x)      // first index with a[i] >= x
{
    int lo = 0, hi = a.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

static int UpperBound(int[] a, int x)      // first index with a[i] > x
{
    int lo = 0, hi = a.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Console.WriteLine();
Console.WriteLine($"a = [{string.Join(", ", a)}]");
foreach (int x in new[] { 20, 25 })
{
    int lb = LowerBound(a, x), ub = UpperBound(a, x);
    Console.WriteLine($"x={x,2}  lower={lb}  upper={ub}  count={ub - lb}");
}

It prints:

BinarySearch(30) =  4   found at index 4
BinarySearch(25) = -5   not found; ~-5 = 4 is where it would go
BinarySearch( 5) = -1   not found; ~-1 = 0 is where it would go
BinarySearch(50) = -7   not found; ~-7 = 6 is where it would go

a = [10, 20, 20, 20, 30, 40]
x=20  lower=1  upper=4  count=3
x=25  lower=4  upper=4  count=0

A negative result is not a failure code. It is ~insertionPoint — the bitwise complement of where the value would go. ~(-5) is 4, so 25 belongs at index 4. That single line replaces a second search in a great many problems.

What Array.BinarySearch will not do is tell you which duplicate you found. With three copies of 20 in the array, the documentation promises only that you get one of them. So the two bounds are worth having by hand, and the pair answers more questions than either alone.

Note both are while (lo < hi) with hi starting at a.Length, not a.Length - 1. That is deliberate — the answer can legitimately be “past the end”, which is what happens for 50.

Cost: O(log n).

Reach for it when you need a count of equal values, an insertion point, or the first element at least as large as some bound. upper - lower is the count, and no separate scan is needed.

Pattern 17 — Binary search on the answer

Here is the one that matters.

Packages have to ship in order, over D days. Pick the smallest daily capacity that gets everything delivered in time.

There is no array to search. But look at the shape of the question. If capacity 20 works, then 21 works, and 22, and everything above. If 14 fails, 13 fails, and everything below. So the answers, laid out in order, look like this:

capacity:  10  11  12  13  14  15  16  17  18  19  20
works?      F   F   F   F   F   T   T   T   T   T   T

That flips exactly once, and finding where something flips exactly once is what binary search is. The sorted array was never the requirement — it was one way of getting this property.

int[] weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
int days = 5;

// Can every package be shipped within `days` at this capacity? Packages must
// go in order, so this is a simple greedy pass.
static bool Feasible(int[] w, int days, int cap)
{
    int used = 1, load = 0;
    foreach (int x in w)
    {
        if (x > cap) return false;
        if (load + x > cap) { used++; load = 0; }
        load += x;
    }
    return used <= days;
}

int lo = weights.Max();          // cannot be less than the heaviest single item
int hi = weights.Sum();          // one day is always enough

Console.WriteLine($"searching capacities {lo}..{hi}\n");

while (lo < hi)
{
    int mid = lo + (hi - lo) / 2;
    bool ok = Feasible(weights, days, mid);
    Console.WriteLine($"lo={lo,2} hi={hi,2}  try {mid,2}  ->  {(ok ? "fits, so nothing bigger is needed: hi = mid" : "too small: lo = mid + 1")}");
    if (ok) hi = mid; else lo = mid + 1;
}

Console.WriteLine($"\nsmallest capacity that works: {lo}");
Console.WriteLine($"check {lo}: {Feasible(weights, days, lo)}   check {lo - 1}: {Feasible(weights, days, lo - 1)}");

It prints:

searching capacities 10..55

lo=10 hi=55  try 32  ->  fits, so nothing bigger is needed: hi = mid
lo=10 hi=32  try 21  ->  fits, so nothing bigger is needed: hi = mid
lo=10 hi=21  try 15  ->  fits, so nothing bigger is needed: hi = mid
lo=10 hi=15  try 12  ->  too small: lo = mid + 1
lo=13 hi=15  try 14  ->  too small: lo = mid + 1

smallest capacity that works: 15
check 15: True   check 14: False

Three things make this work, and they are the checklist for every problem of this shape:

1. A feasibility test. Feasible answers yes or no for one candidate. It is a plain greedy pass, and it is allowed to be slow-ish — it runs only O(log range) times.
2. Monotonicity. Once true, always true going up. If that fails, the whole approach is invalid, and this is the thing to check before writing any code.
3. Bounds that are obviously correct. lo is the heaviest single package, because nothing smaller can ever ship it. hi is the total, because that always finishes in one day. Neither needs to be tight — only right.

The last two printed lines are the habit worth keeping: assert that the answer works and that one below it does not. It catches an off-by-one immediately.

Cost: O(feasibility × log range).

Reach for it when the problem says minimise the maximum, maximise the minimum, or the smallest X such that. That phrasing is close to a guarantee.

Pattern 18 — The rotated array

A sorted array, rotated at an unknown point. Find a target in O(log n).

The instinct is to find the rotation point first, then search. That works, and it is two searches. This is one.

At any split, the rotation break can only fall in one half — there is only one break. So the other half is properly sorted, and you can reason about it normally.

int[] a = [4, 5, 6, 7, 0, 1, 2];

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

        // Exactly one half is guaranteed to be sorted. Find it, then ask
        // whether the target lies inside it.
        if (a[lo] <= a[mid])
        {
            Console.WriteLine($"  lo={lo} mid={mid} hi={hi}  left half [{a[lo]}..{a[mid]}] is sorted");
            if (a[lo] <= target && target < a[mid]) hi = mid - 1; else lo = mid + 1;
        }
        else
        {
            Console.WriteLine($"  lo={lo} mid={mid} hi={hi}  right half [{a[mid]}..{a[hi]}] is sorted");
            if (a[mid] < target && target <= a[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return -1;
}

Console.WriteLine($"a = [{string.Join(", ", a)}]\n");
foreach (int t in new[] { 0, 6, 3 })
{
    Console.WriteLine($"target {t}:");
    Console.WriteLine($"  -> {Search(a, t)}\n");
}

It prints:

a = [4, 5, 6, 7, 0, 1, 2]

target 0:
  lo=0 mid=3 hi=6  left half [4..7] is sorted
  lo=4 mid=5 hi=6  left half [0..1] is sorted
  -> 4

target 6:
  lo=0 mid=3 hi=6  left half [4..7] is sorted
  lo=0 mid=1 hi=2  left half [4..5] is sorted
  -> 2

target 3:
  lo=0 mid=3 hi=6  left half [4..7] is sorted
  lo=4 mid=5 hi=6  left half [0..1] is sorted
  lo=6 mid=6 hi=6  left half [2..2] is sorted
  -> -1

The comparison a[lo] <= a[mid] is not about the target at all. It asks which half is intact. Only then does the target get tested, against that half’s known range.

Watch the target 3 run: it never finds anything, and it still halves the search every step, ending in three comparisons rather than seven.

Cost: O(log n).

Reach for it when the data is sorted but shifted — rotated arrays, circular buffers, a log file that wrapped.

Pattern 19 — Binary search on real numbers

Same idea, continuous domain. There is no “next” value to step to, so the loop cannot terminate on lo == hi.

The wrong fix is while (hi - lo > 1e-9). Near the limits of double precision, (lo + hi) / 2 can equal lo exactly, the interval stops shrinking, and the loop never ends. It passes every test you write and hangs on the judge.

The right fix is to stop counting precision and count iterations.

// A FIXED iteration count, not an epsilon. 100 halvings takes any starting
// interval below 2^-100, which is far under what a double can represent — so
// this cannot spin forever, and it needs no tolerance argument.
static double Root(double x)
{
    double lo = 0, hi = Math.Max(1.0, x);
    for (int it = 0; it < 100; it++)
    {
        double mid = (lo + hi) / 2;
        if (mid * mid < x) lo = mid; else hi = mid;
    }
    return lo;
}

foreach (double x in new[] { 2.0, 10.0, 0.25, 1e6 })
    Console.WriteLine($"root({x,9}) = {Root(x):F10}   Math.Sqrt = {Math.Sqrt(x):F10}");

Console.WriteLine();
Console.WriteLine($"{"iterations",11}  {"interval width",18}");
double w = 1.0;
foreach (int n in new[] { 10, 30, 50, 100 })
{
    w = Math.Pow(2, -n);
    Console.WriteLine($"{n,11}  {w,18:E3}");
}

It prints:

root(        2) = 1.4142135624   Math.Sqrt = 1.4142135624
root(       10) = 3.1622776602   Math.Sqrt = 3.1622776602
root(     0.25) = 0.5000000000   Math.Sqrt = 0.5000000000
root(  1000000) = 1000.0000000000   Math.Sqrt = 1000.0000000000

 iterations      interval width
         10          9.766E-004
         30          9.313E-010
         50          8.882E-016
        100          7.889E-031

A hundred halvings takes any starting interval down by a factor of 2⁻¹⁰⁰, which is around 7.9 × 10⁻³¹ — far below anything a double can represent. So a hundred iterations is always enough, costs nothing, and cannot loop forever. Fifty is usually plenty. Use a hundred and stop thinking about it.

Cost: O(iterations), a fixed constant.

Reach for it when the answer is a real number — a rate, a ratio, a distance, a time.

Pattern 20 — Ternary search, when the answer is not monotonic

Binary search needs the yes/no answer to flip once. Some problems do not give you that. A function that falls and then rises has no flip point — it has a minimum, and on both sides of it the function is going the wrong way.

One probe cannot tell you which side of the minimum you are on. Two can.

// Unimodal: falls, then rises. Binary search needs monotonic, which this is
// not — but the minimum can still be bracketed, by comparing two interior
// points instead of one.
static double F(double x) => (x - 2.5) * (x - 2.5) + 1;

double lo = 0, hi = 10;
for (int it = 0; it < 200; it++)
{
    double m1 = lo + (hi - lo) / 3;
    double m2 = hi - (hi - lo) / 3;
    if (F(m1) < F(m2)) hi = m2; else lo = m1;
    if (it < 4)
        Console.WriteLine($"it={it}  m1={m1:F4} f={F(m1):F4}   m2={m2:F4} f={F(m2):F4}   -> [{lo:F4}, {hi:F4}]");
}

double x = (lo + hi) / 2;
Console.WriteLine($"\nminimum at x = {x:F8}, f(x) = {F(x):F8}");

It prints:

it=0  m1=3.3333 f=1.6944   m2=6.6667 f=18.3611   -> [0.0000, 6.6667]
it=1  m1=2.2222 f=1.0772   m2=4.4444 f=4.7809   -> [0.0000, 4.4444]
it=2  m1=1.4815 f=2.0374   m2=2.9630 f=1.2143   -> [1.4815, 4.4444]
it=3  m1=2.4691 f=1.0010   m2=3.4568 f=1.9154   -> [1.4815, 3.4568]

minimum at x = 2.50000001, f(x) = 1.00000000

Now look closely at that answer: x = 2.50000001, but f(x) = 1.00000000.

The function value is right to sixteen digits while the location is only right to eight. That is not a bug in the loop, and more iterations will not fix it. Near a minimum a smooth function is flat, so a huge range of x produces values that a double cannot tell apart. The location is only ever recoverable to about the square root of machine epsilon.

If the problem asks for the minimum value, ternary search is exact. If it asks where the minimum is, you get half the digits.

Cost: O(iterations) — each step keeps two thirds of the interval, so it converges more slowly than binary search but still geometrically.

Reach for it when the quantity clearly falls and then rises. Unimodal is the requirement, and it is a real one — on a function with two dips, this converges confidently to the wrong one.

What to remember

• A negative Array.BinarySearch result is ~insertionPoint. Not an error. Apply ~ and you have where it belongs.

• lower and upper bounds answer questions the BCL search cannot. upper - lower is how many copies exist, and equality means absent.

• Binary search does not need a sorted array. It needs a yes/no question that flips exactly once. That is a much weaker requirement, and it is why the pattern applies to problems containing no collection at all.

• Check monotonicity before writing anything. If “works at 20” does not imply “works at 21”, the search is invalid no matter how carefully it is coded.

• Loose bounds are fine; wrong bounds are not. The heaviest item and the total sum are both obviously correct, and O(log) makes the slack free.

• On real numbers, count iterations, not precision. A hundred is always enough and can never hang. An epsilon condition can.

• Ternary search locates a minimum to half the digits it evaluates it to. Flatness near the minimum, not a coding error.

Part 5 moves from searching to the containers: stacks, queues, and the monotonic structures that answer “what is the next bigger thing” in one pass.