Array.BinarySearch
The .NET Array type provides a BinarySearch
generic method. This method determines the location of an element in the array.
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.
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.
string
literals. The array variable is a reference to this data in memory.Array.BinarySearch
. In this example the type is inferred on all 3 calls.Array.BinarySearch
method calls. The correct indexes were found.using System; // Part 1: source array that is ordered ascending. string[] array = { "a", "e", "m", "n", "x", "z" }; // Part 2: 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); // Part 3: write results. Console.WriteLine(index1); Console.WriteLine(index2); Console.WriteLine(index3);2 4 1
This next program benchmarks Array.BinarySearch
against Array.FindIndex
. It generates a string
array of 10000 random file names and sorts them.
for
-loop uses Array.BinarySearch
to locate an element. The array is always sorted, so this works.Array.FindIndex
. This method would work on an unsorted array.Array.BinarySearch
method was over 40 times faster than Array.FindIndex
.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
The binary search algorithm in computer science has much better performance than a linear search in most nontrivial cases.
Dictionary
or hash table on string
keys.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.