Wednesday, May 18, 2011

Binary Search

Binary search adds a small bit of overhead for a large performance gain. The basic input for binary search is that the collection is kept in a sorted manner before the search happens. A telephone book is the best example for a large scale binary search.

The concept of binary search is simple: In a sorted list where each element supports comparability, search for the target element in the middle. If the target value is less, discard the right half of the list and if the target is more, discard the left half. Continue this process with the remaining half till the element is found or the search element does not exist.

Linear search is a brute force approach. Binary search is more in the category of Divide and conquer. The best case performance is same as linear search: O(1). But the average and worst case performance actually becomes O(log n) which is exponentially better than linear search. Consider this: Binary search divides the the size of the problem in half every iteration.

Now let's look at one possible solution. In this example, I would like to introduce to you 3 advanced concepts from the .NET world: Generics, Generic constraints and the IComparable<T> interface.  Any object implementing the IComparable interface guarantees that it's elements will be comparable to each other in a meaningful way. Let's look at the code now:

`using System;namespace SimpleCodingQuestions{    /// <summary>    /// Perform Binary Search given a pre-sorted list     /// of elements that implenent the IComparable interface     /// </summary>    /// <typeparam name="T">type of elements being searched</typeparam>    public class BinarySearch<T> where T: class, IComparable<T>    {        public static bool Search(T[] input, T target)        {            // null's cannot exist            if (target == null)                return false;                        // define the search range            int low = 0;            int high = input.Length - 1;            // divide and conquer the list now            while (low <= high)            {                // find the mid point                int mid = (low + high)/2;                // compare the mid element with target                int compareResult = target.CompareTo(input[mid]);                if (compareResult < 0)                {                    // discard right and recompare in left                    high = mid - 1;                }                else if (compareResult > 0)                {                    // value is more than mid                    // discard left and recompare in right                    low = mid + 1;                }                else                {                    // we found our guy                    return true;                }            }            // element not found            return false;        }    }}`

Binary search is good in cases where the collection is not modified often as that would require a re-sorting (or inserting in a sorted manner) each time a new element is inserted or deleted. In the next post, we will discuss another method of searching: Hash based search.