Binary Search: Easy to Explain, Difficult to Code

Our second Algorithm Friday, here's the results of the first, was an overall success. This week we looked into a search algorithm called binary search. Even though our implementations of the algorithm were messy, and we failed multiple times, we learned a hell of a lot more than we had expected. Primarily, what we didn't actually know. Wikipedia's entry on binary search says the following:
In computer science, a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value. For binary search, the array should be arranged in ascending or descending order.

This means that binary search is a very efficient search algorithm. It's worst case efficiency is O(log n), and it's best case is O(1). The algorithm works by splitting the array to be searched into two equal parts, and gets the index of the middle element. This index is commonly referred to as the pivot. So the pivot is there in the middle now. The algorithm needs to check if the value stored at the pivot index is the target, and if not, whether the target is greater than or less than that value. If it's greater, the search start index changes to the pivot, and the algorithm calls itself recursively with the 2nd half of the total array. This continues until the target is found, or it's determined that the target does not exist within the array.

An implementation of this algorithm through code could look similar to this:

function binarySearch(array, target, startIndex, stopIndex) {  
  // Pivot becomes the middle index of the array
  pivot = Math.floor((stopIndex + startIndex) / 2);
  // If start and stop are the same, or they are one apart, stop searching.
  // This indicates that the array is fully searched, and the target hasn't been found.
  if (stopIndex == startIndex || Math.abs(stopIndex - startIndex) == 1) {
    document.getElementById('result').innerHTML = 'not found';
    return;
  } else { // Otherwise, search the array.
    if (array[pivot] == target) {
      // Target has been found at the pivot's index.
      document.getElementById('result').innerHTML = pivot;
      return;
    } else {
      if (target < array[pivot]) {
        // Recursively call the search with the bottom half.
        stopIndex = pivot;
        binarySearch(array, target, startIndex, stopIndex);
      } else {
        // Recursively call the search with the top half.
        startIndex = pivot;
        binarySearch(array, target, startIndex, stopIndex);
      }
    }
  }
}

The key of this algorithm, outside of the recursion, is this line: pivot = Math.floor((stopIndex + startIndex) / 2); This makes sure that they pivot is in the center of the array, and it updates to the center after each subsequent split.

You can see a live example of this search on my webpage.

Also here is a nice video with a more in depth explanation:

So that's it. Conceptually binary search is not too terribly complicated, but it's implementation is very powerful. Hopefully this rambling has explained at least a little about the awesomeness that is binary search. If you have any questions or find something wrong with my code please leave a comment below.

comments powered by Disqus