C# 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.

Example

First we see how you can use the Array.BinarySearch method in your 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. In fact, in this example the type is inferred on all three methods and the old, non-generic method in the library is never used.

This C# example program uses the Array.BinarySearch method. It searches an array.

Program that uses Array.BinarySearch method [C#]

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

Program text overview. The program begins in the Main entry point and an array containing six strings of one letter each is allocated on the managed heap. The array variable is simply a reference to this data in memory. The Array.BinarySearch method is used with three different 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 method calls to point to the generic method in the base class library called BinarySearch. It basically ignores the missing <string> type parameter in this case and infers that you want the string type method in all three cases. You can verify this by disassembling the compiled program. Internally, this method uses the classic binary search algorithm.

Performance

The binary search algorithm in computer science has much better performance than a linear search in most non-trivial cases. However, my testing shows that in C# its performance is far worse than a Dictionary or hash table on string keys. Sometimes when memory usage is important, binary search can help improve that metric. You can find a detailed benchmark on binary search here.

Summary

We looked at the powerful Array.BinarySearch method in the C# programming language and .NET Framework. 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. We did not cover the basics of the binary search algorithm, which you can find in more authoritative textbooks.