C# - Array.BinarySearch Method

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.

Array

Generic

List BinarySearch

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.

Part 1 We allocate an array containing 6 string literals. The array variable is a reference to this data in memory.

String Literal

Part 2 We call Array.BinarySearch. In this example the type is inferred on all 3 calls.

Part 3 We print the results from the 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

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.

Array.Find

Result The 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

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.

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.