C# BinarySearch ListUse the BinarySearch method on a sorted List to quickly locate an element in the List.
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 and output:
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.
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.
© 2007-2022 sam allen.
see site info on the changelog.