C# List - Linear Search vs Binary Search

List is a very commonly used and an effective generic collection of .NET framework. Apart from being dynamic that helps you keep adding entries at runtime without having to worry about the size, List also provides you many other options like searching, sorting, manipulating. etc.

In this post, I am going to explain two types of Search that you can perform with System.Collections.Generic.List class.

1. Linear Search

2. Binary Search

Linear Search vs Binary Search

Linear Search searches every element in a list one at a time and in sequence starting from the first element. In complexity term it is O(n), where n is the number of elements in the list. It is useful and fast when we have small number of elements in the list. Since, the amount of effort needed is in proportion with the count of the list being searched, it takes more time to perform sequential search when the count is large.

Binary Search on the other hand starts from the middle of a sorted list and decides on which half of the list to proceed in order to find the element to be searched. By doing it this way it eliminates half of the list on every routine until it finds an exact match. In complexity term it takes O(log n)time to complete. 

Now if you are looking for an answer on which one to use in your application, in order to have a performance effective search operation, my answer is 'it depends upon the size of the list'. Binary search is an amazing algorithm, which can produce search results in worst case 10 steps for a list that contains 1000 elements, whereas Linear search would take 1000 steps worst case. Yet linear search is best for lists that have less number of elements because binary search can never work on an unsorted list. Sorting data is quite costly in terms of time, even the fastest sorting algorithm has O(n * log n) time complexity. So you have to decide carefully on which type of search to use in your application. Sorting a large list that contains millions of elements to perform a single binary search is not a wiser option. Choose binary search only if you have to do frequent searches on the list.

C# List Linear Search Examples

Contains Method

System.Collections.Generic class provides Contains method to find whether an item you are searching for is present at least once in the Collection. It returns a boolean value indicating whether the value that you are searching for is present or not.This method performs a linear search starting from the first element and uses Equals method to compare values. See the following example for better understanding.

using System.Collections.Generic;

class Program

{

static void Main()

{

List<int> list = new List<int>(new int[] { 7, 9, 11 });

bool result=list.Contains(9);

Console.WriteLine(result);

}

}

Output:

True

There is a LINQ Contains method that accepts an additional IEqualityComparer instance along with the search term. This enables you to specify how elements should be compared for equality. For example, if you want to ignore case while searching for a string value, then you can use StringComparer.OrdinalIgnoreCase class that implements IEqualityComparer interface to tell the Contains method to ignore case while searching.

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

List<string> list = new List<string>(new string[] 

                             { "Exe","Text", "Zip", "Doc" });

bool result = list.Contains

                     ("text",StringComparer.OrdinalIgnoreCase);

Console.WriteLine(result);

}

}

Output:

True

Find Method

Find method enables you to find the first element with a value that satisfies a specific condition from your list. It takes a Predicate as a parameter, which can also be specified using lambda expression. In the following example, find method does a forward search and returns the first element that satisfies the condition specified in the lambda expression.

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

List<string> list = new List<string>(new string[] 

                             { "Exe","Text","Zip","Doc" });

string searchterm = "Text";

string result=list.Find(s => s == searchterm);

Console.WriteLine(result);

}

}

Output:

Text

FindLast Method

If you want to do a backward search and return the last matching element then FindLast method does the job for you.

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

List<int> list = new List<int>(new int[] { 7,9,11,23,27 });

int result=list.FindLast(k=>k > 11);

Console.WriteLine(result);

}

}

Output:

27

FindAll Method

FindAll method returns collection of all matching values in the list.

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

List<int> list = new List<int>(new int[] { 7,9,11,23,27 });

List<int> filter=list.FindAll(i=> i >=11);

foreach(var k in filter)

{

Console.WriteLine(k);

}

}

}

Output:

11

23

27

Exists Method

Exists Method is similar to that of Contains method except it takes a Predicate as an argument. It returns a boolean value indicating whether an element that satisfies the lambda expression is present in the list or not.

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

List<int> list = new List<int>(new int[] { 7,9,11,23,27 });

bool result=list.Exists(j=>j<9);

Console.WriteLine(result);

}

}

Output:

True

C# List Binary Search Example

BinarySearch Method

BinarySearch method uses binary search algorithm to perform search on a sorted list. This is useful when you have large number of elements in the list. It returns the index of the value that matches the search term.

using System.Collections.Generic;

class Program

{

static void Main()

{

List<string> list = new List<string>(new string[] 

                             { "Exe","Text","Zip","Doc" });

string searchterm = "Zip";

list.Sort();

int indexnumber = list.BinarySearch("Zip");

Console.WriteLine(indexnumber);

}

}

Output:

3

Please leave your comments and queries about this post in the comment sections in order for me to improve my writing skills and to showcase more useful posts.

Subscribe to GET LATEST ARTICLES!