« The Plea of Democracy In The Electoral College | Home | What The Sony PSP Really Needs »

Lessons In Algorithms: Binary Search

This is the first entry in the ‘Lessons In Algorithms’ series here at The Angry Walrus! As time passes more entries will be added to the series. In the series I will briefly introduce an algorithm along with simple example code, with an explanation of how it works.

The Vitals:

1. Category: Search Algorithm
2. Name: Binary Search
3. Data Structure Used: Array
4. Speed: O(log n)

The Algorithm

In a nutshell, the Binary Search algorithm – also known as the ‘binary chop’ – is a method for finding the location of a specific value in an array that has already been sorted by ‘chopping’ the array into progressively smaller halves. I was first introduced to this algorithm during my High School CS class where we used it to search for entries in a phone book application that we had written. This specific algorithm’s strengths lie in the fact that it’s quite speedy, and at the same time very easy to implement and understand. The only concession you have to make when using this algorithm is that it can only be used on an array that has been previously sorted.

How it works

The way the algorithm itself functions is rather quite simple. It starts with a high value, a low value, and a middle value. The high value is the array’s size, the middle value is the median, and the low value is the location in the array where the lowest value is, which is 0 – because arrays start at zero! The algorithm then makes a check to see if the value we want is equal to, greater than, or less than or median value. If the value we want is, for example, less than the value in our median index, we set the new high value to that median index – and then compute a new median location based on the size of our new chunk of array; the same process happens if the value we want is greater than the value at the median index – we would set the ‘low’ location to that index and recompute another median just as before. What this does with each iteration, is progressively cut the section of array we are searching in half!

Eventually, after cutting our array subsections in half over and over again, the value stored at the median location will be the same as the value we are searching for. We can then return the array index that holds our value. As you probably can imagine, because the algorithm effectively cuts the amount of data in half each iteration it would be well suited for large data sets.

I have created a simple mock up to demonstrate how this algorithm would be put together and used in C++:

int binarySearch(int array[], int size, int number)
{     
	//'found' will eventually hold the position our number is located in
	int found = -1; 
	int low = 0; int high = size;
	int mid = static_cast<int>(high/2);
 
	while((found == -1) && (mid != low))
	{
		if(number < array[mid]) 
		{
			high = mid;
		}
		else{
			low = mid;                      
		}
		if(number == array[mid]){
			found = mid;
		}                                                     
		mid = (high + low)/2;     
	}//end while
	if((low == mid) && (array[low] == number)){
		found = low;
	}
 
	return found;
}//end function

Similar Posts:

None Found