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.

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.

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.

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.

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.