The Beauty of Binary Searches – Xojo Programming Blog

Problem: you need to search an array to see if it contains a particular value. The simple solution is IndexOf if it’s a simple array, or a loop like this:

for each item as ArrayType in myArray
  if item.Matches( myValue ) then
    YesSiree( myValue )
    exit
  end if
next

That’s pretty easy, but what if the array is really big? And what if you have to do this many times?

For example, let’s say your array has 10,000 items. For each value that doesn’t match, your code will have to do 10,000 comparisons. But, if your array can be sorted, you can perform that task with, at most, 14 comparisons using a binary search.

The concept is simple: you take an ordered list and start in the middle. If what you’re trying to match is less than that point, you discard the upper half of the list, then start again at the midpoint of the rest. By continuously cutting the list in half, you will do, at most, Ceil(Log2(arrayCount)) comparisons per value.

For simplicity’s sake, let’s say you want to search an array of strings. (Yes, a Dictionary would be the better choice here, but this is just for illustration.) The code would look something like this:

myArray.Sort

var firstIndex as integer = 0
var lastIndex as integer = myArray.LastIndex

while firstIndex <= lastIndex
  var midPoint as integer = ( lastIndex - firstIndex ) \ 2 + firstIndex

  var compare as string = myArray( midPoint )

  if myValue = compare then
    YesSiree( myValue )
    exit
  end if

  if myValue < compare then
    lastIndex = midPoint - 1
  else
    firstIndex = midPoint + 1
  end if
wend

With that 10,000-item array, the first loop would look at item 5,000. If myValue is greater than that, it would next look at item 7,500. Still greater? Now it will look at item 8,750, and so on. The entire array will be processed efficiently with large chunks never needing examination at all. If you have to do this for 1,000 different values, you will end with, at most, 14,000 comparisons instead of 10 million.

Quite the savings, right?

Kem Tekinay is a Mac consultant and programmer who has been using Xojo since its first release to create custom solutions for clients. He is the author of the popular utilities TFTP Client and RegExRX (both written with Xojo) and lives in Connecticut with his wife Lisa, and their cat.