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.