C#

Generic Binary Search in C#

Programmingempire

Today I will explain the Generic Binary Search in C#. Basically, Binary Search is a technique that is used to find a target value from a list of values.

In general, Binary Search takes a list of values as input and searches for a target value by dividing the list into two equal halves in each direction. In this process, it compares the target value with the element at the middle position and returns the index of the middle value if a match is found.

However, if the match is not found, this algorithm discards one half of the list and continues the search in the other half. Specifically, if the target value is less than the middle value, it will be searched in the first half and the second half of the list is discarded. On the other hand, if the target value is more than the middle value, the first half of the list is discarded, and searching continues in the second half of the list.

Implementing Binary Search in C#

While implementing the Binary Search algorithm usually, create a list of values such as an array. As can be seen, the list may consist of either numbers or strings. A C# implementation of Binary Search can be found here.

BinarySearch Method of Generic List Class

The List<T> class defined in the namespace System.Collections.Generic has a method called BinarySearch that applies the binary search algorithm on the elements of the List<T>. Of course, the list should be sorted before searching using binary search.

The above-mentioned method has three overloads which we describe below.

  • BinarySearch(T) method performs searching using the default implementation of the IComparer interface.
  • Besides the default implementation, another overload BinarySearch(T, IComparer<T>) allows us to specify our own implementation of the IComaparer interface.
  • Further, List<T> class has one more overload of this method that allows us to perform searching on a specific part of the list – BinarySearch(Int32, Int32, T, IComparer<T>)

Example of Generic Binary Search in C#

Basically, there are many situations where we need to provide a custom implementation of the IComparer interface and that too on a user-defined type. For instance, suppose a customer searches for an item in an online store. Therefore, the search function should allow searching on a variety of features of a particular item.

As an illustration, the following example shows the implementation of the IComparer interface for the three fields of the type EthnicClothes. Hence, it allows users to search an item on any of the three attributes.

Likewise, we create a generic List using the objects of class EthnicClothes and perform binary search using an object of this class as the target element.

Further, we sort the list before performing search using a specific IComparer object and then perform binary search using the same object.

using System;
using System.Collections.Generic;
namespace GenericBinarySearch
{
    class EthnicClothes
    {
        public string ItemName { get; set; } = "Saree";
        public int price { get; set; } = 3000;
        public string color { get; set; } = "Red";
        public override string ToString()
        {
            return $"Item Name: {ItemName}, Color: {color}, Price: {price}";
        }
    }
    class CompareNames: IComparer<EthnicClothes>
    {
        public int Compare(EthnicClothes ob1, EthnicClothes ob2)
        {
            string s1 = ob1.ItemName;
            string s2 = ob2.ItemName;
            return s1.CompareTo(s2);
        }
    }
    class CompareColors : IComparer<EthnicClothes>
    {
        public int Compare(EthnicClothes ob1, EthnicClothes ob2)
        {
            string s1 = ob1.color;
            string s2 = ob2.color;
            return s1.CompareTo(s2);
        }
    }
    class ComparePrice : IComparer<EthnicClothes>
    {
        public int Compare(EthnicClothes ob1, EthnicClothes ob2)
        {
            int x = ob1.price;
            int y = ob2.price;
            int v=0;
            if (x < y) v= -1;
            if (x > y) v= 1;
            if (x == y) v= 0;
            return v;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<EthnicClothes> list1 = new List<EthnicClothes>();
            list1.Add(new EthnicClothes { ItemName = "Churidaar", color = "Red", price =500 });
            list1.Add(new EthnicClothes { ItemName = "Saree", color = "Pink", price =380 });
            list1.Add(new EthnicClothes { ItemName = "Saree", color = "Blue", price =5000 });
            list1.Add(new EthnicClothes { ItemName = "Saree", color = "Green", price =1000 });
            list1.Add(new EthnicClothes { ItemName = "Lehnga", color = "Violet", price =12000 });
            list1.Add(new EthnicClothes { ItemName = "Saree", color = "Purple", price =8000 });
            list1.Add(new EthnicClothes { ItemName = "Lehnga", color = "Orange", price =4000 });
            list1.Add(new EthnicClothes { ItemName = "Churidaar", color = "Yellow", price =600 });
            list1.Add(new EthnicClothes { ItemName = "Churidaar", color = "White", price =900 });
            list1.Add(new EthnicClothes { ItemName = "Salwar Kameez", color = "Navy", price =1200 });
            list1.Add(new EthnicClothes { ItemName = "Salwar Kameez", color = "Magenta", price =1400 });
            list1.Add(new EthnicClothes { ItemName = "Saree", color = "Peach", price =700 });

            Console.WriteLine("Sorted List on ItemName...");
            list1.Sort(new CompareNames());
            foreach (var ob in list1)
                Console.WriteLine(ob);
            Console.WriteLine("nn");
            EthnicClothes e1 = new EthnicClothes { ItemName = "Saree" };
            int i = list1.BinarySearch(0, list1.Count, e1, new CompareNames());
            Console.WriteLine("Item Found at the index: "+i);
            Console.ReadLine();
            Console.Clear();

            Console.WriteLine("Sorted List on color...");
            list1.Sort(new CompareColors());
            foreach (var ob in list1)
                Console.WriteLine(ob);
            Console.WriteLine("nn");
            EthnicClothes e2 = new EthnicClothes { color = "Pink" };
            i = list1.BinarySearch(0, list1.Count, e2, new CompareColors());
            Console.WriteLine("Item Found at the index: " + i);
            Console.ReadLine();
            Console.Clear();

            Console.WriteLine("Sorted List on price...");
            list1.Sort(new ComparePrice());
            foreach (var ob in list1)
                Console.WriteLine(ob);
            EthnicClothes e3 = new EthnicClothes { price = 1000 };
            i = list1.BinarySearch(0, list1.Count, e3, new ComparePrice());
            Console.WriteLine("Item Found at the index: " + i);
        }
    }
}

Output

Generic Binary Search in C#
Searching Item Name using Generic Binary Search in C#

As can be seen, binary search retrieves the index of the target element and it need not be necessarily the first occurrence.

Searching Item Color using Generic Binary Search in C#
Searching Item Color using Generic Binary Search in C#

Now that, we have an IComparer for the color field so we can use it to perform searching.

Searching Item Price using Generic Binary Search in C#
Searching Item Price using Generic Binary Search in C#

Likewise, the above output shows performing binary search on the price field.

Summary

This article on Generic Binary Search in C# explains the BinarySearch() method of the generic List<T> class. Also, an example of performing search on a collection of user-defined type with implementation of IComparer on its different fields is also presented.


programmingempire

You may also like...