HomeSearch

C# Array.BinarySearch Method

This C# example program uses the Array.BinarySearch method. It searches an array.
Array.BinarySearch. The Array type provides a BinarySearch generic method. This method quickly and accurately pinpoints the location of an element in the array. It can be told how to compare elements. It works correctly only on a presorted array.ArrayGeneric Class, Method
First, we use the Array.BinarySearch method. This method has one version that accepts a type parameter, which you can specify in angle brackets. The C# compiler will infer this type.

Note: In this example the type is inferred on all three methods and the old, non-generic method in the library is never used.

Main: An array containing 6 strings is allocated on the managed heap. The array variable is simply a reference to this data in memory.

String Literal

Next: BinarySearch is used with 3 parameter lists. The type parameter <string> is specified in the second 2 invocations.

Overload: The C# compiler translates the 3 Array.BinarySearch calls to point to the generic method in the base class library called BinarySearch.

IL Disassembler
C# program that uses Array.BinarySearch method 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); } } Output 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. Please see the GetArray() method in the sample.Path.GetRandomFileName

Loops: The first for-loop uses Array.BinarySearch to locate that element. The second uses Array.FindIndex.

ForModulo

Also: An exception is thrown if the results are invalid. So we know the method is returning the correct results.

Result: The Array.BinarySearch method was over 40 times faster than Array.FindIndex.

Array Find

Note: Array.FindIndex uses a predicate, which will reduce performance. And other solutions, such as a Dictionary, will be faster still.

Dictionary
C# program that tests Array.BinarySearch 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(); 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(); 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")); Console.Read(); } } Output 1336.09 ns BinarySearch 57243.46 ns FindIndex
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.

BinarySearch List
However, in most programs, BinarySearch is not worth considering. In my experience it is usually best to use Dictionary. This eliminates many concerns about pathological lookup performance.
Summary. We looked at the powerful Array.BinarySearch method. We saw how the C# compiler infers type parameters on this method and how you can compare elements based on a StringComparer class. Finally, we noted the performance of this method.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Home
Dot Net Perls