Binary search in C#

Here is a generic implementation of binary search in C#. It can be used to sort any kind of list as long as the elements implement the IComparable interface.


         /// <summary>
         /// Searches through a list using binary search algorithm
         /// </summary>
         /// <param name="source"></param>
         /// <param name="searchKey"></param>
         /// <returns></returns>
         public static int BinSearch<T>(this List<T> source, T searchKey)
             where T:IComparable
         {
             int low = 0;
             int high = source.Count - 1;
             int mid;

             do
             {
                 mid = low + ((high - low) / 2);

                 int compareResult = searchKey.CompareTo(source[mid]);

                 //If item is at current mid position we can stop
                 if(compareResult == 0)
                 {
                     return mid;
                 }
                 //Otherwise look at either lower half or upper half of the list
                 else
                 {
                     //If searchKey < source[mid] then we need to look at
                     //left half of the list
                     if(compareResult < 0)
                     {
                         high = mid - 1;
                     }
                     else
                     {
                         low = mid + 1;
                     }
                 }
             } while (low < high);

             return -1;
         }

The entire code is available here.

Sample output

Enter source list:
6 7 9 11 67 98 123 156
Enter number to search for:
67
Output of binary search: 4

Enter source list:
6 7 8 9 11
Enter number to search for:
11
Output of binary search: 4

Enter source list:
1 3 6 7 8
Enter number to search for:
4
Output of binary search: -1

Lessons learned

  • Extension methods cannot be written for static classes (I tried to extend System.Console)
  • IComparable.CompareTo() returns values as follows for objA.CompareTo(objB):
    • 0 if objA == objB
    • >1 if objA > objB
    • <1 if objA < objB
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