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.
| Property | Value |
|---|---|
| Time | O(log n) |
| Extra memory | O(1) |
| Requirement | data 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.
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.
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.
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.
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.
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.
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.
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.
#: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#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
- Bucket sort
- Array.Sort and Span.Sort
- Stable sorting
- Introsort
- Quickselect
- External sort
- Timsort
Author
List all C# tutorials.