C# Array.BinarySearch Method

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.

Generic Method

Example. First we learn how to use the Array.BinarySearch method in C# programs. The Array.BinarySearch method has one version that accepts a type parameter, which you can specify in angle brackets.

However: The C# compiler will infer this type for you so you can omit it if the source code is clearer to you that way.

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

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

The program begins in the Main entry point. An array containing six string literals of one letter each 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 three parameter lists. The type parameter <string> is specified in the second two invocations.

What overloads are used? The C# compiler translates the three Array.BinarySearch calls to point to the generic method in the base class library called BinarySearch. It basically ignores the missing <string> type parameter.

So: It infers that you want the string type method in all three cases. You can verify this by disassembling the compiled program.

IL Disassembler

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.GetRandomFileNameString Array

Then, it shows two for-loops. These use modulo division to get an element from the random string array. The first for-loop uses Array.BinarySearch to locate that element. The second uses Array.FindIndex.

ForModulo Operator

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.FindIndex

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.

Collections

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.

But: We did not cover the basics of the binary search algorithm, which you can find in more authoritative textbooks.

Related Links