C# BinarySearch List

You are evaluating the BinarySearch method on List or arrays, and want data on whether it can improve your program. You have a variable number of elements in your collection. Binary search is an amazing algorithm that 'hones' in on values in sorted collections. It has O(log n) complexity, making it more efficient than others in the C# language.

Using BinarySearch

First, here we look at an example program that uses the BinarySearch instance method on the List type. You must pass this method a value of the type used in the List. Normally, programs use strings, so we use that type here.

=== Program that uses BinarySearch (C#) ===

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> l = new List<string>();
        l.Add("acorn");      // 0
        l.Add("apple");      // 1
        l.Add("banana");     // 2
        l.Add("cantaloupe"); // 3
        l.Add("lettuce");    // 4
        l.Add("onion");      // 5
        l.Add("peach");      // 6
        l.Add("pepper");     // 7
        l.Add("squash");     // 8
        l.Add("tangerine");  // 9

        // This returns the index of "peach".
        int i = l.BinarySearch("peach");
        Console.WriteLine(i);

        // This returns the index of "banana".
        i = l.BinarySearch("banana");
        Console.WriteLine(i);

        // This returns the index of "apple".
        i = l.BinarySearch("apple");
        Console.WriteLine(i);
    }
}

=== Output of the program ===

6
2
1

Description. Three values are looked up. The locations of "peach", "banana", and "apple" are looked up in the List. Note that the List is in alphabetical order. BinarySearch won't work if your List or array is not already sorted. It doesn't matter if you use numeric, alphanumeric, or ASCII sorting.

Benchmark

I found here that binary search becomes more efficient in comparison to a linear search with large collections. For small collections of less than about 100 elements, BinarySearch is slower, probably due to implementation overhead.

Understanding BinarySearch

Here we note that Wikipedia states that binary search "makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span." [Binary Search Algorithm - Wikipedia] MSDN states that the BinarySearch method on List, which we will use, "returns the zero-based index of the element" we request. However, we must use a sorted List.

(Visit msdn.microsoft.com.)

What about Dictionary?

Here we mention that Dictionary is a hashtable with a constant lookup time. It is faster than List with any search algorithm on the data I used. Clearly, you should choose Dictionary for most scenarios. Looking at the benchmark, though, we can see that as the number of elements grows, BinarySearch becomes more efficient than a linear search.

Dealing with large collections. With huge collections, such as ones with millions of elements, the cost of building up a Dictionary could eclipse the time saved on lookup. However, I find this uncommon.

Summary

Here we saw how you can use the BinarySearch instance method on the List type in the C# programming language. BinarySearch uses a better algorithm than iterative searches for large collections, but normally falls short of Dictionary. I suggest that you take measurements any time you consider BinarySearch. You can find more information on the internal Array.BinarySearch method that is used in the .NET Framework here.

(See Array.BinarySearch Method.)

(Do not copy this page.)