Home
Search
C# Array.BinarySearch MethodUse the Array.BinarySearch method to find an element in a sorted array.
dot net perls
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.
Array
Generic Class, Method
BinarySearch List
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.
Main An array containing 6 strings is allocated on the managed heap. The array variable is 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.
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); } }
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.
Path.GetRandomFileName
Version 1 The first for-loop uses Array.BinarySearch to locate an element. The array is always sorted, so this works.
For
Version 2 The second version uses Array.FindIndex. This method would work on an unsorted array.
Result The Array.BinarySearch method was over 40 times faster than Array.FindIndex.
Array Find
Also An exception is thrown if the results are invalid. So we know the method is returning the correct results.
Exception
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(); // 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")); Console.Read(); } }
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.
Warning In most programs, BinarySearch is not worth considering. In my experience it is usually best to use Dictionary.
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.
Home
© 2007-2021 sam allen. see site info on the changelog