Binary search in C#
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
BinarySearch.cs, 32 lines- Level
- Toolchain
- .NET 10, C# 14, xUnit
- Test framework
- xUnit
- Run the tests
dotnet test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
namespace Algorithm;
/// <summary>Binary search in a sorted array.</summary>
public static class BinarySearch
{
/// <summary>Returns an index i with a[i] == x, or -1 when x is not in a. The array must be sorted.</summary>
public static int Search<T>(ReadOnlySpan<T> a, T x) where T : IComparable<T>
{
int lo = 0, hi = a.Length; // @line L1
while (lo < hi) // @line L2
{
int mid = lo + (hi - lo) / 2; // @line L3
int c = a[mid].CompareTo(x);
if (c < 0) // @line L4
{
lo = mid + 1; // @line L5
}
else if (c > 0) // @line L6
{
hi = mid; // @line L7
}
else
{
return mid; // @line L8
}
}
return -1; // @line L9
}
}
BinarySearchTests.cs 45 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
using Algorithm;
using Xunit;
public class BinarySearchTests
{
[Theory]
[InlineData(23, 5)]
[InlineData(2, 0)]
[InlineData(91, 9)]
[InlineData(30, -1)]
[InlineData(1, -1)]
[InlineData(100, -1)]
public void Examples(long x, int want)
{
long[] a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
Assert.Equal(want, BinarySearch.Search<long>(a, x));
}
[Fact]
public void Edges()
{
Assert.Equal(-1, BinarySearch.Search<long>(Array.Empty<long>(), 1));
Assert.Equal(0, BinarySearch.Search<long>(new long[] { 7 }, 7));
Assert.Equal(1, BinarySearch.Search<string>(new[] { "ant", "bee", "cat" }, "bee"));
}
[Fact]
public void RandomAgainstLinearScan()
{
var rng = new Random(2150);
for (int t = 0; t < 2000; t++)
{
var a = new long[rng.Next(31)];
for (int i = 0; i < a.Length; i++) a[i] = rng.Next(41) - 20;
Array.Sort(a);
long x = rng.Next(51) - 25;
int got = BinarySearch.Search<long>(a, x);
if (Array.IndexOf(a, x) >= 0) Assert.Equal(x, a[got]);
else Assert.Equal(-1, got);
}
}
}
What the next level needs
- the native tests did not run in this build
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work