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 pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.