C# BinarySearch List

Use the BinarySearch method on a sorted List to quickly locate an element in the List.

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

Notes, algorithm. 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.

Example. Here we use the BinarySearch 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.

Here: Three values are looked up. The locations of "peach", "banana", and "apple" are looked up in the List.

Important: The List is in alphabetical order. BinarySearch won't work if your List or array is not already sorted.

And: It doesn't matter if you use numeric, alphanumeric, or ASCII sorting—BinarySearch will work with any of these.

C# program that uses BinarySearch 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 6 2 1

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.

Info: Wikipedia states that binary search "makes progressively better guesses, and closes in on the location of the sought value."

Binary search algorithm: Wikipedia

Note: Microsoft states that the BinarySearch method on List, which we will use, "returns the zero-based index of the element" we request.

List.BinarySearch Method: Microsoft Docs

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.

Dictionary

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

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# BinarySearch List

Related Links:

.Net

Java

Related Links