TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

C# BinarySearch List

This C# example program demonstrates the BinarySearch method on Lists.

BinarySearch optimizes searches on sorted collections.

We evaluate the BinarySearch method on List and arrays. We may have a variable number of elements. Binary search is an amazing algorithm that hones in on values in sorted collections.

Complexity: Binary search has O(log n) complexity, making it more efficient than others.

Example. Here we look at an example program that uses the BinarySearch instance 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.

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

Three values are looked up. The locations of "peach", "banana", and "apple" are looked up in the List. Note that 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.

Discussion. I found here that 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, probably due to implementation overhead.

Wikipedia states that binary search "makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the span." See "Binary Search Algorithm" on Wikipedia.

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

List.BinarySearch Method: MSDN

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. 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.

Summary. We used the BinarySearch instance method on the List type in the C# language. BinarySearch uses a better algorithm than iterative searches for large collections, but normally falls short of Dictionary.

Tip: It is worthwhile to take measurements any time you consider the BinarySearch method.

Array.BinarySearch Method


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf