Binary search in C#

Problem

The filter that reads the whole catalog

The shop has 1,000,000 products, and the price list is sorted by price. The "exact price" filter searches with a loop from the start, like linear search. The prices in the code are in euro cents: from 2 to 2,000,000. A customer looks for a product at €20,000.01, and there is none:

int n = 1_000_000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;

int comparisons = 0;
int found = -1;
for (int i = 0; i < n; i++)
{
    comparisons++;
    if (prices[i] == target)
    {
        found = i;
        break;
    }
}
Console.WriteLine("Index: " + found);
Console.WriteLine("Comparisons: " + comparisons);

Index: -1
Comparisons: 1000000

A million comparisons to say "none". And every time the page opens, the filter runs for dozens of prices.

The prices are sorted, and the loop does not use that. When you look up a word in a dictionary, you do not read from the first page. You open it in the middle and see whether the word comes before or after.

The idea

Ask the middle, throw away half

Look at the price in the middle of the price list:

if it is the one you want, you are done;
if it is smaller, the one you want can only be to the right. The left half drops out, together with the middle;
if it is larger, the one you want can only be to the left.

Then the same with the half that is left. This is binary search. The range where the price can still be is kept with two indexes: lo (the start) and hi (the end). The middle is mid.

Every comparison halves the range. 1,000,000 prices become 500,000, then 250,000, and after about 20 halvings one is left. How many times you divide by 2 until you reach 1 is called the base-2 logarithm: log₂ 1,000,000 ≈ 20. That is why binary search is O(log n), and linear search is O(n).

There is one condition: the array must be sorted. In an unsorted array "it is smaller, so it is to the right" is not true.

See it

lo, mid and hi in the price list

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

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
Console.WriteLine("Index: " + Find(prices, 49));

Index: 12

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

Step by step, in words

The price list is sorted: 15 prices. We look for €49. lo and hi cover everything, from 0 to 14.
mid = 7: €27 < €49, so the price is to the right. lo = 8, the left part drops out. 7 prices are left.
mid = 11: €44 < €49, so the price is to the right. lo = 12, the left part drops out. 3 prices are left.
mid = 13: €53 > €49, so the price is to the left. hi = 12, the right part drops out. 1 price is left.
mid = 12: €49. That is the price we want: find returns 12.
4 comparisons. A search from the start would have looked at 13 prices; for 1 000 000 prices binary search needs at most 20.

The middle is lo + (hi - lo) / 2, not (lo + hi) / 2. Both give the same number, but the second can overflow. Why is on one of the next cards.

More precisely, if you are curious

The worst case is when the price is not there: the range is halved until lo passes hi. For n prices that is at most ⌊log₂ n⌋ + 1 comparisons: 4 for 10 prices, 10 for 1000, 20 for 1,000,000. The best case is one comparison: the price is right in the middle.

Here a "comparison" is one probe of mid. The check for equal and the check for smaller are two lines in the code, but they ask about the same price.

Try it

Predict how many probes

Sorted prices in euro cents: 2, 4, 6, …, 2000. We look for 2001, and there is no such price. How many times does the loop run?

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;

int steps = 0;
int lo = 0;
int hi = n - 1;
while (lo <= hi)
{
    int mid = lo + (hi - lo) / 2;
    steps++;
    if (prices[mid] == target)
    {
        break;
    }
    else if (prices[mid] < target)
    {
        lo = mid + 1;
    }
    else
    {
        hi = mid - 1;
    }
}
Console.WriteLine(steps);

Answer

Try it

Fill in

The price at mid is smaller than the one you want. Where does the new range start?

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

The idea

The boundaries: where everyone gets it wrong

Binary search takes six lines to write, and it is known for being written wrong. The mistake is almost always off by one: < instead of <=, mid instead of mid - 1. It is called an off-by-one error.

You guard against it with one decision: what lo and hi mean. Then you keep to it everywhere.

Closed range [lo, hi]: both ends may be the price. hi starts at the last index, the loop runs while lo <= hi, and the middle is thrown away with hi = mid - 1 and lo = mid + 1. That is find from above.
Half-open range [lo, hi): hi is the first place after the range. hi starts at the length of the array, the loop runs while lo < hi, and you go left with hi = mid, because hi is not in the range anyway.

Both are right. The mistake is mixing them. Here is a closed range with hi = mid from the half-open one. We look for €4, and there is no such price. A guard stops the loop after 8 probes; otherwise it would never stop:

static int Find(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length - 1;
    int probes = 0;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        Console.WriteLine($"lo={lo} hi={hi} mid={mid}");
        if (++probes == 8)
        {
            Console.WriteLine("Stopping after 8 probes: lo and hi do not move");
            return -1;
        }
        if (prices[mid] == target)
        {
            return mid;
        }
        else if (prices[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid;
        }
    }
    return -1;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
Find(prices, 4);

lo=0 hi=14 mid=7
lo=0 hi=7 mid=3
lo=0 hi=3 mid=1
lo=0 hi=1 mid=0
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
Stopping after 8 probes: lo and hi do not move

When lo and hi become 1, the middle is 1, the price there is €5, more than €4, and hi = mid is 1 again. Nothing changes. This is an infinite loop: the program does not crash, it hangs.

Try it

Find the bug

The search finds €49, but it does not find the most expensive product, €58, even though it is in the price list:

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
Console.WriteLine("Index: " + Find(prices, 58));

Index: -1

Pick the line with the bug.

The idea

When (lo + hi) / 2 overflows

An int in C# goes up to 2,147,483,647. An array with more than a billion elements is rare, but it happens: a file index, a log, an in-memory database. Then lo + hi can pass the limit:

int lo = 1_500_000_000;
int hi = 2_000_000_000;
Console.WriteLine((lo + hi) / 2);
Console.WriteLine(lo + (hi - lo) / 2);
Console.WriteLine((lo + hi) >>> 1);

-397483648
1750000000
1750000000

The sum is 3,500,000,000. It does not fit in an int, and C# gives no error: it wraps it into a negative number. The middle becomes -397,483,648, and index -397,483,648 throws an exception. lo + (hi - lo) / 2 computes the same thing without adding: the difference always fits. (lo + hi) >>> 1 is the other way: >>> shifts the bits right, treating the number as non-negative, and that is division by 2.

More precisely, if you are curious

The bug is not made up. The binary search in the Java standard library, Arrays.binarySearch, had (low + high) / 2 for nine years. Joshua Bloch described it in 2006 in the article "Nearly All Binary Searches and Mergesorts are Broken": a program with an array of more than 2³⁰ elements crashes with ArrayIndexOutOfBoundsException. Today it says (low + high) >>> 1 there.

C# has had the >>> operator since version 11. Array.BinarySearch in .NET computes the middle with lo + ((hi - lo) >> 1).

See it

The first price from €20 up

The "price from €20" filter does not look for an exact price. It looks for the first place where the price is at least €20: from there on are all the products it has to show. This is called the lower bound. It is also the first occurrence: if the prices have three products at €15, the lower bound of 15 is the first of them.

find does not give it: it stops at the first 15 it steps on. The lower bound uses a half-open range, and the loop does not stop on equal, it keeps going left:

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

int[] prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49];
Console.WriteLine("Find: " + Find(prices, 15));
int first = LowerBound(prices, 15);
Console.WriteLine("The first €15: index " + first);
Console.WriteLine("Products at €15: " + (LowerBound(prices, 16) - first));
int from20 = LowerBound(prices, 20);
Console.WriteLine($"The first price from €20 up: €{prices[from20]}");

Find: 5
The first €15: index 4
Products at €15: 3
The first price from €20 up: €24

If the price is smaller than the one you want, it and everything before it drop out: lo = mid + 1. Otherwise mid may be the answer, so it stays in the range: hi = mid. The loop ends when lo and hi meet, and there is the first place with a price ≥ the one you want. If there is no such place, lo is the length of the array. How many products cost €15 is the difference between two lower bounds: of 16 and of 15.

C# has a ready-made binary search: Array.BinarySearch for an array and List<T>.BinarySearch for a sorted list. When the price is not there, it returns the bitwise complement of the place where it would go: ~i turns it back:

int[] prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49];
Console.WriteLine(Array.BinarySearch(prices, 24));
int i = Array.BinarySearch(prices, 20);
Console.WriteLine(i);
Console.WriteLine(~i);
Console.WriteLine(Array.BinarySearch(prices, 15));

With duplicates Array.BinarySearch returns one of the equal ones, without promising which: for €15 it gives 5, while the first is at 4. For the lower bound you write your own method, like LowerBound.

See it

Measure it: linear against binary

Linear and binary search in the same sorted price list, when the price is not there. Linear search compares every price: n comparisons. Binary search makes 20 comparisons for 1,000,000 prices:

Linear search (every price) O(n)
Binary search O(log n)

Algorithm	n = 10	n = 1,000	n = 100,000	n = 1,000,000
Linear search (every price)	10	1,000	100,000	1,000,000
Binary search	4	10	17	20

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

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

The binary curve almost lies flat: with 100 times more prices it rises by about 7 comparisons. That is why binary search is everywhere something is sorted: database indexes, git bisect, finding the version where a test started to fail.

Exercise

The price filter: from €10 to €30

Solve it in your editor.

From €10 to €30. The filter shows how many products cost from €10 to €30 inclusive. The price list is sorted: €3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 and 49. Do not walk the whole array: with two binary searches find the first place with a price ≥ €10 and the first with a price ≥ €31. The difference is the count.

From €10 to €30: 7 products

More tasks

The last occurrence. Write UpperBound: the first place with a price larger than the one you want. The last product at €15 is one place before it.
A free delivery slot. The free delivery slots are a sorted array of minutes after midnight (540 is 9:00). The customer wants delivery no earlier than 14:10. Find the first free slot, or say there is none.
Where the new price goes. A new product at €21 has to go into the price list so that it stays sorted. Find the place with binary search.

Test

Check yourself

1. The price list has 1,000,000 prices, sorted by size. At most how many comparisons does binary search make?500,000100020

2. The range is closed: hi starts at the last index. Which loop condition is right?lo <= hilo < hilo != hi

3. With while (lo <= hi) someone writes hi = mid instead of hi = mid - 1. What happens?Nothing, the search is only a bit slowerThe program does not compileWhen lo and hi meet and the price at mid is larger, hi stays the same and the loop never stops

4. The prices have three products at €15. Which one do you look for to show every product "from €15 up"?The first place with a price ≥ €15 (the lower bound)The last €15Whichever 15 binary search finds

5. The product list is not sorted. Can you use binary search?Yes, if the list is smallYes, it is only slowerNo: the answer is wrong, because the half you throw away may hold the price

Binary search

Cookies