ZetCode

C# binary search

last modified November 15, 2026

In this article we search sorted data in C# with binary search. We use the built-in Array.BinarySearch and List.BinarySearch methods, interpret their negative results, implement the algorithm ourselves, and write lower and upper bound functions for data with duplicates.

Binary search algorithm

Binary search finds a value in a sorted array by repeatedly halving the search interval. It compares the target with the middle element. If they are equal, the search is over. If the target is larger, the search continues in the right half, otherwise in the left half.

PropertyValue
TimeO(log n)
Extra memoryO(1)
Requirementdata sorted by the same comparer

Each step halves the interval, so a million elements need at most 20 comparisons. A linear search needs half a million on average.

Array.BinarySearch

The Array.BinarySearch method returns the index of the found element. If the element is not found, it returns a negative number: the bitwise complement of the index where the element would be inserted.

Program.cs
int[] nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

int idx = Array.BinarySearch(nums, 23);
Console.WriteLine($"23 found at index {idx}");

idx = Array.BinarySearch(nums, 40);
Console.WriteLine($"40: result {idx}, insert at {~idx}");

idx = Array.BinarySearch(nums, 1);
Console.WriteLine($"1: result {idx}, insert at {~idx}");

idx = Array.BinarySearch(nums, 100);
Console.WriteLine($"100: result {idx}, insert at {~idx}");

idx = Array.BinarySearch(nums, 3, 4, 16);
Console.WriteLine($"16 in range [3..7) at index {idx}");

We search for elements that are present and for elements that are not.

idx = Array.BinarySearch(nums, 40);
Console.WriteLine($"40: result {idx}, insert at {~idx}");

Value 40 belongs between 38 and 56, at index 7. The method returns ~7, which is -8. The ~ operator turns it back into 7. The complement is used instead of a plain negation, because -0 would be indistinguishable from a found element at index 0.

idx = Array.BinarySearch(nums, 100);

A value larger than all elements gives the complement of the array length.

idx = Array.BinarySearch(nums, 3, 4, 16);

This overload searches only four elements starting at index 3. The returned index is relative to the whole array.

$ dotnet run
23 found at index 5
40: result -8, insert at 7
1: result -1, insert at 0
100: result -11, insert at 10
16 in range [3..7) at index 4

Keeping a list sorted

The insertion point lets us keep a list sorted while adding elements.

Program.cs
List<string> words = [];

foreach (var w in new[] { "pear", "apple", "fig", "plum", "kiwi", "apple", "banana" })
{
    int idx = words.BinarySearch(w, StringComparer.Ordinal);

    if (idx >= 0)
    {
        Console.WriteLine($"{w} already present at {idx}");
        continue;
    }

    words.Insert(~idx, w);
}

Console.WriteLine(string.Join(" ", words));

We insert words into a list at the position returned by BinarySearch and skip duplicates.

int idx = words.BinarySearch(w, StringComparer.Ordinal);

List<T>.BinarySearch works like the array method.

words.Insert(~idx, w);

The search is O(log n), but Insert shifts all following elements and is O(n). For many insertions, a SortedSet<T> or sorting once at the end is faster.

$ dotnet run
apple already present at 0
apple banana fig kiwi pear plum

Implementing binary search

The next example implements binary search and prints the search interval in each step.

Program.cs
int[] nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

Console.WriteLine(BinarySearch(nums, 72));
Console.WriteLine();
Console.WriteLine(BinarySearch(nums, 13));

static int BinarySearch(int[] arr, int target)
{
    int lo = 0;
    int hi = arr.Length - 1;

    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        Console.WriteLine($"lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}");

        if (arr[mid] == target) return mid;

        if (arr[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }

    return ~lo;
}

The method returns the same values as Array.BinarySearch.

int mid = lo + (hi - lo) / 2;

The middle index is computed as lo + (hi - lo) / 2. The shorter (lo + hi) / 2 overflows when the sum exceeds int.MaxValue; this bug was present in the Java library for almost ten years.

if (arr[mid] < target)
{
    lo = mid + 1;
}
else
{
    hi = mid - 1;
}

The middle element has been checked, so the next interval excludes it.

return ~lo;

When the interval is empty, lo points to the first element greater than the target, which is the insertion point.

Finding 72 takes three steps, deciding that 13 is missing takes four. The missing value would be inserted at index 4, so the method returns -5.

$ dotnet run
lo=0 hi=9 mid=4 arr[mid]=16
lo=5 hi=9 mid=7 arr[mid]=56
lo=8 hi=9 mid=8 arr[mid]=72
8

lo=0 hi=9 mid=4 arr[mid]=16
lo=0 hi=3 mid=1 arr[mid]=5
lo=2 hi=3 mid=2 arr[mid]=8
lo=3 hi=3 mid=3 arr[mid]=12
-5

Lower and upper bound

If the array contains duplicates, BinarySearch returns the index of one of them; which one is not specified. The lower bound is the index of the first element not less than the value; the upper bound is the index of the first element greater than the value.

Program.cs
int[] scores = [55, 60, 60, 60, 60, 60, 60, 72, 72, 80, 80, 80, 91];

Console.WriteLine($"BinarySearch(60): {Array.BinarySearch(scores, 60)}");
Console.WriteLine($"BinarySearch(80): {Array.BinarySearch(scores, 80)}");

Console.WriteLine($"LowerBound(60): {LowerBound(scores, 60)}");
Console.WriteLine($"UpperBound(60): {UpperBound(scores, 60)}");
Console.WriteLine($"count of 60: {UpperBound(scores, 60) - LowerBound(scores, 60)}");

int from = LowerBound(scores, 70);
int to = UpperBound(scores, 85);
Console.WriteLine($"scores in [70, 85]: {string.Join(" ", scores[from..to])}");

static int LowerBound(int[] arr, int value)
{
    int lo = 0, hi = arr.Length;

    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] < value) lo = mid + 1;
        else hi = mid;
    }

    return lo;
}

static int UpperBound(int[] arr, int value)
{
    int lo = 0, hi = arr.Length;

    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] <= value) lo = mid + 1;
        else hi = mid;
    }

    return lo;
}

The scores array contains six 60s.

Console.WriteLine($"BinarySearch(60): {Array.BinarySearch(scores, 60)}");

Array.BinarySearch returns 6, the last of the 60s. For 80 it returns 9, the first one.

if (arr[mid] < value) lo = mid + 1;
else hi = mid;

The lower bound never stops at a match; it keeps moving left while the middle element is not less than the value. The interval is half-open, so hi starts at arr.Length and the result can be the array length.

if (arr[mid] <= value) lo = mid + 1;

The upper bound differs only in the comparison.

int from = LowerBound(scores, 70);
int to = UpperBound(scores, 85);

The two bounds give the number of occurrences of a value and all elements in a range of values, both in O(log n) time.

$ dotnet run
BinarySearch(60): 6
BinarySearch(80): 9
LowerBound(60): 1
UpperBound(60): 7
count of 60: 6
scores in [70, 85]: 72 72 80 80 80

Custom comparers and keys

Arrays of objects are searched with the comparer that was used to sort them. Span search can look up a key without creating a whole object.

Program.cs
Person[] people =
[
    new("Peter", 23), new("Lucy", 29), new("Robert", 34),
    new("Anna", 41), new("Tom", 52), new("Jane", 67),
];

var byAge = Comparer<Person>.Create((a, b) => a.Age.CompareTo(b.Age));
int idx = Array.BinarySearch(people, new Person("", 41), byAge);
Console.WriteLine($"age 41: {people[idx]}");

ReadOnlySpan<Person> span = people;
idx = span.BinarySearch(new AgeKey(52));
Console.WriteLine($"age 52: {people[idx]}");

idx = span.BinarySearch(new AgeKey(30));
Console.WriteLine($"age 30: not found, next older is {people[~idx]}");

string[] names = ["anna", "Lucy", "peter", "Robert"];
Console.WriteLine($"ordinal search for Peter: {Array.BinarySearch(names, "Peter", StringComparer.Ordinal)}");
Console.WriteLine($"ignore-case search for Peter: {Array.BinarySearch(names, "Peter", StringComparer.OrdinalIgnoreCase)}");

record Person(string Name, int Age);

readonly struct AgeKey(int age) : IComparable<Person>
{
    public int CompareTo(Person? other) => age.CompareTo(other!.Age);
}

The people are sorted by age.

int idx = Array.BinarySearch(people, new Person("", 41), byAge);

Array.BinarySearch needs a value of the element type, so we create a dummy person with the searched age.

idx = span.BinarySearch(new AgeKey(52));

The MemoryExtensions.BinarySearch method accepts any value that implements IComparable of the element type. The AgeKey struct compares an age with a person.

Console.WriteLine($"ordinal search for Peter: {Array.BinarySearch(names, "Peter", StringComparer.Ordinal)}");

The names are sorted ignoring case. An ordinal search does not find Peter, because the comparer decides what equal means. Moreover, the array is not in ordinal order (uppercase letters come first in ordinal order), so the ordinal search could miss elements that are present.

$ dotnet run
age 41: Person { Name = Anna, Age = 41 }
age 52: Person { Name = Tom, Age = 52 }
age 30: not found, next older is Person { Name = Robert, Age = 34 }
ordinal search for Peter: -3
ignore-case search for Peter: 2

Searching unsorted data

Binary search on unsorted data does not throw an exception. It returns wrong answers.

Program.cs
int[] nums = [8, 3, 12, 5, 1, 9, 20, 7];

foreach (int x in nums)
{
    int idx = Array.BinarySearch(nums, x);
    Console.Write($"{x}:{(idx >= 0 ? "found" : "MISSING")} ");
}

Console.WriteLine();

Array.Sort(nums);

foreach (int x in nums)
{
    int idx = Array.BinarySearch(nums, x);
    Console.Write($"{x}:{(idx >= 0 ? "found" : "MISSING")} ");
}

Console.WriteLine();

We search for every element of an array before and after sorting it.

Before sorting, half of the elements that are in the array are reported as missing. Keep data sorted at all times or sort it before searching.

$ dotnet run
8:MISSING 3:found 12:MISSING 5:found 1:MISSING 9:found 20:found 7:MISSING 
1:found 3:found 5:found 7:found 8:found 9:found 12:found 20:found 

Binary search on the answer

Binary search works on any monotonic condition, not only on arrays. If a condition is false up to some point and true afterwards, binary search finds that point.

Program.cs
Console.WriteLine(Isqrt(99));
Console.WriteLine(Isqrt(100));
Console.WriteLine(Isqrt(long.MaxValue));

int[] temps = [-3, -1, 2, 4, 7, 11, 15];
int first = FirstTrue(0, temps.Length, i => temps[i] > 5);
Console.WriteLine($"first temperature above 5: {temps[first]} at index {first}");

static long Isqrt(long n)
{
    long lo = 0, hi = 3_037_000_499;

    while (lo < hi)
    {
        long mid = lo + (hi - lo + 1) / 2;

        if (mid * mid <= n) lo = mid;
        else hi = mid - 1;
    }

    return lo;
}

static int FirstTrue(int lo, int hi, Func<int, bool> pred)
{
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;

        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

We compute an integer square root and find the first element that satisfies a condition.

long lo = 0, hi = 3_037_000_499;

The square root of long.MaxValue is below 3,037,000,500. This upper limit keeps mid * mid from overflowing.

long mid = lo + (hi - lo + 1) / 2;

if (mid * mid <= n) lo = mid;
else hi = mid - 1;

We look for the largest number whose square is not greater than n. When lo can be assigned mid, the middle has to be rounded up; otherwise the loop would not end for an interval of two elements.

if (pred(mid)) hi = mid;
else lo = mid + 1;

The FirstTrue function returns the first index for which the predicate is true. It is the general form of the lower bound.

$ dotnet run
9
10
3037000499
first temperature above 5: 7 at index 4

Performance

In the last example, we look up 10,000 values in a sorted array of one million integers.

benchmark.cs
#:property PublishAot=false

using System.Diagnostics;

var rnd = new Random(17);
int[] data = [.. Enumerable.Range(0, 1_000_000).Select(_ => rnd.Next())];
Array.Sort(data);

int[] queries = [.. Enumerable.Range(0, 10_000).Select(_ => data[rnd.Next(data.Length)])];
var set = new HashSet<int>(data);

var sw = Stopwatch.StartNew();
int found = 0;
foreach (int q in queries) if (Array.IndexOf(data, q) >= 0) found++;
Console.WriteLine($"Array.IndexOf:      {sw.Elapsed.TotalMilliseconds,8:F2} ms ({found} found)");

sw.Restart();
found = 0;
foreach (int q in queries) if (Array.BinarySearch(data, q) >= 0) found++;
Console.WriteLine($"Array.BinarySearch: {sw.Elapsed.TotalMilliseconds,8:F2} ms ({found} found)");

sw.Restart();
found = 0;
foreach (int q in queries) if (set.Contains(q)) found++;
Console.WriteLine($"HashSet.Contains:   {sw.Elapsed.TotalMilliseconds,8:F2} ms ({found} found)");

We compare a linear search with Array.IndexOf, binary search, and a HashSet.

Array.IndexOf is vectorized, but it still scans half of the array on average. Binary search is more than 200 times faster. A hash set is faster still, but it takes extra memory and cannot answer range queries or find the nearest element.

$ dotnet run -c Release benchmark.cs
Array.IndexOf:        433.99 ms (10000 found)
Array.BinarySearch:     1.89 ms (10000 found)
HashSet.Contains:       0.42 ms (10000 found)

Source

Array.BinarySearch method
List<T>.BinarySearch method
MemoryExtensions.BinarySearch method

In this article we have searched sorted data with binary search in C#.

Other sorting articles in C#:

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.