Array.BinarySearch. The Array type provides a BinarySearch generic method. This method quickly and accurately pinpoints the location of an element in the array.
Some details. This method can be told how to compare elements. It works correctly only on a presorted array. It can help a rare program that needs binary search.
First example. We use Array.BinarySearch. This method has one version that accepts a type parameter, which we can specify in angle brackets. The C# compiler will infer this type.
Note In this example the type is inferred on all 3 methods and the old, non-generic method in the library is never used.
Detail An array containing 6 strings is allocated on the managed heap. The array variable is a reference to this data in memory.
Next BinarySearch is used with 3 parameter lists. The type parameter string is specified in the second 2 invocations.
Detail The C# compiler translates the 3 Array.BinarySearch calls to point to the generic method in the base class library.
using System;
class Program
{
static void Main()
{
//// Source array that is ordered ascending.//
string[] array = { "a", "e", "m", "n", "x", "z" };
//// Call versions of the BinarySearch method.//
int index1 = Array.BinarySearch(array, "m");
int index2 = Array.BinarySearch<string>(array, "x");
int index3 = Array.BinarySearch<string>(array, "E", StringComparer.OrdinalIgnoreCase);
//// Write results.//
Console.WriteLine(index1);
Console.WriteLine(index2);
Console.WriteLine(index3);
}
}2
4
1
Benchmark. This next program benchmarks Array.BinarySearch against Array.FindIndex. It generates a string array of 10000 random file names and sorts them.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
class Program
{
static string[] GetArray()
{
List<string> list = new List<string>();
for (int i = 0; i < 10000; i++)
{
list.Add(Path.GetRandomFileName());
}
string[] array = list.ToArray();
Array.Sort(array);
return array;
}
const int _max = 10000;
static void Main()
{
string[] array = GetArray();
var s1 = Stopwatch.StartNew();
// Version 1: use BinarySearch.
for (int i = 0; i < _max; i++)
{
int index1 = i % 10000;
string key = array[index1];
int index2 = Array.BinarySearch<string>(array, key);
if (index1 != index2)
{
throw new Exception();
}
}
s1.Stop();
var s2 = Stopwatch.StartNew();
// Version 2: use FindIndex.
for (int i = 0; i < _max; i++)
{
int index1 = i % 10000;
string key = array[index1];
int index2 = Array.FindIndex(array, element => element == key);
if (index1 != index2)
{
throw new Exception();
}
}
s2.Stop();
Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns"));
}
} 1336.09 ns BinarySearch
57243.46 ns FindIndex
A discussion. The binary search algorithm in computer science has much better performance than a linear search in most nontrivial cases.
However My testing shows that its performance is far worse than a Dictionary or hash table on string keys.
Tip Sometimes when memory usage is important, binary search can help improve that metric.
Detail In most programs, BinarySearch is not worth considering. In my experience it is usually best to use Dictionary.
A summary. The C# compiler infers type parameters on Array.BinarySearch. We can compare elements based on a StringComparer class. Finally, we noted the performance of this method.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Jan 25, 2022 (edit).