Binary Search Algorithm in C#


Binary search is another well known searching algorithm. In plain terms, a binary search starts at the midpoint of a list or collection and compares a search term or key with the midpoint term, so in example:

List = 1, 4, 6, 8, 10, 18, 32    Value to look for: X = 4

First run: compare X with 8 (the middle value). Its smaller, repeat search with 1, 4, 6
Second run: compare X with 6. Its smaller, repeat with 1, 4
Third run: compare X with 4. Search is done, we have found 4.

  • The Binary search has O(log(n)) complexity, making it more efficient in the long run with larger data collections unlike the Linear Sort which is more desirable with smaller, unsorted data collections. Its O(log(n)) because it halves the number of items to search with each iteration
  • For a binary search to begin, the collection MUST be sorted first and foremost

The binary search implementation:

class Program
    {
        static void Main()
        {
            int[] collection = { 1, 3, 5, 7, 9, 11, 21 }; //our collection is already sorted
            for (int i = 0; i < collection.Length; i++)
            {
                Console.Write("{0} ", collection[i]);
            }//first, we write all the elements of the collection on the window so we can see the list
            Console.WriteLine();

            Console.Write("Enter a value to search for in the collection: ");
            int searchKey = int.Parse(Console.ReadLine());

            int middle;
            int maximum = collection.Length;
            int minimum = 0;
            while (minimum <= maximum)
            {
                middle = (maximum + minimum) / 2;
                if (collection[middle] == searchKey)
                {
                    Console.WriteLine("\nElement {0} was found at position {1} in the collection!", searchKey, middle);
                    break;
                }
                else if (collection[middle] > searchKey)
                {
                    maximum = middle - 1;
                }
                else if (collection[middle] < searchKey)
                {
                    minimum = middle + 1;
                }
                else
                {
                    Console.WriteLine("The value does not exist");
                    break;
                }
            }

            Console.ReadLine();
        }
    }

Further illustrations:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s