BinarySearch

This C# method optimizes searches on sorted collections. We evaluate the BinarySearch method on List and arrays. We may have a variable number of elements.

Algorithm notes

Binary search hones in on values in sorted collections—but its usefulness is often limited. Binary search has O(log n) complexity, making it more efficient than others.

Input and output

When we use binary search, we must have a sorted list. We can find a value (like "peach") in 3 values, and the correct index is returned.

Input:               apple, banana, peach
BinarySearch(peach): 2

Example code

Here we use the BinarySearch method on the List type. You must pass this method a value of the type used in the List. Programs often use strings, so we use that type here.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var data = new List<string>() { "banana", "peach", "apple" };

        // Part 1: ensure list is sorted.
        data.Sort();
        Console.WriteLine(string.Join(",", data));

        // Part 2: test the results of BinarySearch.
        int i = data.BinarySearch("peach");
        Console.WriteLine(i);

        i = data.BinarySearch("banana");
        Console.WriteLine(i);

        i = data.BinarySearch("apple");
        Console.WriteLine(i);
    }
}
apple,banana,peach
2
1
0

Discussion

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.

Notes, dictionary

Dictionary has a constant lookup time. It is faster than List with any search algorithm on the data I used. You should choose Dictionary for most scenarios.

A summary

We used the BinarySearch instance method on the List type. BinarySearch uses a better algorithm than iterative searches for large, sorted collections.