Please navigate to the bottom of the page for Table of Contents

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.

7 comments:

  1. Hi There,


    10/10 !!! Thank you for making your blogs an embodiment of perfection and simplicity. You make everything so easy to follow.

    This is my code. In the call to new B(), first the constructor for A is called and setI() is in there. Why it calls B.setI() while executing the constructor of A?
    Java Code:
    1
    public class Test {
    public static void main(String[] args) {
    new A();
    new B();
    }
    }

    class A {
    int i = 0;
    public A() {
    System.out.println("Constr A");
    setI(5);
    }
    public void setI(int i) {
    System.out.println("set in A");
    this.i = 2 * i;
    }
    }
    class B extends A {
    public B() {
    System.out.println("Constr B");
    }

    It was cool to see your article pop up in my google search for the process yesterday. Great Guide.
    Keep up the
    good
    work!


    Thank you,

    ReplyDelete
  2. Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. Binary options recovery

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Binary Options Trading Strategy PDF does not guarantee winnings. However, it helps increase your chances of maximizing your potential profits.

    ReplyDelete
  5. Big thanks to you for sharing such great information.
    user experience company

    ReplyDelete