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.
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.
Part 1 We create a List with 3 string elements, and Sort() it. An unsorted list will not work with BinarySearch.
Part 2 Three values are looked up. The locations of the strings (peach, banana, apple) are looked up in the List.
Important It does not matter if you use numeric, alphanumeric, or ASCII sorting—BinarySearch will work with any of these.
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.
Info As the number of elements grows, BinarySearch is faster than a linear search.
And With huge collections, with millions of elements, the cost of building up a Dictionary could eclipse the time saved on lookup.
A summary. We used the BinarySearch instance method on the List type. BinarySearch uses a better algorithm than iterative searches for large, sorted collections.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
