a blog by Christian Snodgrass
about programming, web and game design, and everything else

Classics to Remember: Binary Search

If you went to school for programming, you’ve likely seen the binary search algorithm. If you’re self taught, as many great programmers are, you may not have come across it before.

What is the Binary Search Algorithm?

The binary search algorithm is an algorithm which searches through a collection of sorted values. It does so by starting in the middle, and divides the number of values it needs to check by two each time.

It’s an algorithm that’s existed for a long time and is still great. Why? It’s all about efficiency.

Efficiency

If you compare it to a linear search (the type of search you perform when you just loop through something), you have a best case of 1 checks, a worst case of n-cases, and an average case of n/2 cases, where n is the number of elements you have to check. This means that if you have 10,000 items to check, you may have to go through the loop 10,000 times.

Conversely, since a binary search divides the number of elements to check in two each time, you have a best case of 1, a worst case of log2n, and an average case of log2n/2. This means the [em]worst-case[/em] scenario for 10,000 items is only 14 checks. That’s a savings of 9,986 loops!

The savings also gets greater as your set gets bigger. Check out this table for a few values:

Linear Worst-Case Binary Worst-Case Savings
20,000 15 19,985
100,000 17 99,983
500,000 19 499,981
1,000,000 20 999,980
1,000,000,000 30 999,999,970

That’s some serious savings.

Did I Mention Sorted?

So, there is a catch to this. The set of data (usually an array) must be sorted. If you try to just throw things together and then sort it right before you need to search, you lose a lot of the efficiency because you have to do a ton of loops to get it sorted.

However, if you keep it sorted, you can get all the perks with almost none of the drawbacks… more on this in a bit.

Recursive

The best way to implement this algorithm is to make a recursive function. Just in case you aren’t familiar with recursive functions, it basically just means it’s a function that repeatedly calls itself to find a solution.

How It Works

The function is fairly straight forward. At the start of the function you find the mid value, which is the average of the min and max indexes which are passed to the function (for recursion). You then check the value at the mid index.

The Function

This algorithm is so useful, I’ll show you how to implement it in ActionScript 3, PHP, and JavaScript.

ActionScript 3

// This uses an array and a * target, but I  
//  highly recommend you use an appropriate 
//  variable type for target and a vector of that 
//  type if you're using this in a limited 
//  manner. 
public function BinarySearch(values:Array, target:*, min:int, max:int):int { 
    if(max < min) 
        return -1; 
  
    // Notice it's a mid, so any decimal 
    //  would be dropped. 
    var mid:int = (max - min) / 2; 
  
    if(target < values[mid]) 
        return BinarySearch(values, target, min, mid - 1); 
    else if(values[mid] < target) 
        return BinarySearch(values, target, mid + 1, min); 
 
    // If we make it this far, we found it! 
    return mid; 

JavaScript

function BinarySearch(values, target, min, max) { 
     if(max < min) 
         return -1; 
 
     var mid = Math.floor((max - min)/2); 
 
     if(target < values[mid]) 
         return BinarySearch(values, target, min, mid - 1); 
     else if(values[mid] < target) 
         return BinarySearch(values, target, mid + 1, max); 
 
     return mid; 

PHP

function BinarySearch($values, $target, $min, $max) { 
    if($max < $min) 
        return -1; 
 
    $mid = floor(($max - $min)/2); 
 
    if($target < $values[$mid]) 
        return BinarySearch($values, $target, $min, $mid - 1); 
    else if($values[$mid] < $target) 
        return BinarySearch($values, $target, $mid + 1, $max); 
    return $mid; 

Using the Function

To use the function, you simply call the function, passing the array of values, the value you’re looking for, 0 (for min), and the length of the array – 1 for the max.

It’ll then return the index of the target value in the array, or -1 if the value doesn’t exist in the array.

So, that Sorted Thing

I said I’d mention this again later. The simple way to keep it sorted would be to loop through the array each time and find the appropriate place.

However, you can create kind of an inverse binary search where you search for the place to insert the value into an array. The function I came up to do this is along the same lines as the binary search, but it’s a bit more complex so I’m going to give it it’s own post. Look for it in the next few days!


Related Articles


Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Back to Top