C# Array.BinarySearch Method

Use the Array.BinarySearch method to find an element in a sorted 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.

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.

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.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(); } } Output 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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Array.BinarySearch Method

Related Links:

.Net

Java

Related Links