Binary Search: Speed up your searches!

Sam Gorick — Wed, 02 Sep 2020 20:07:45 +0000

Say you had to determine whether 15 was in the array below, without using a built-in method. How would you do it?

array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]

One way would be to go through each value in the array, check if it was equal to 15, and return true if so. Something like this:

for i in 0...array.length do
   if array[i] == search
        return true
   end
end

Easy enough. But linear search has a worst-case time complexity of O(N), meaning in a worst-case scenario (say we were looking for 21, or a value that doesn't exist like 10) we would have to compare every single element.

Not too bad for an array of 11 items, but not great if it was 100M values long. That's 100M potential comparisons!

Enter Binary Search. So powerful, it will find any value in a 100M length array in a maximum of 27 comparisons. How come?

The key feature of our array is that it is already sorted. If we pick the middle value, we know that everything to the left is less or equal, and everything to the right is greater or equal.

array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
# middle value is 11

If we're searching for 15, we can make one comparison with the midpoint 11. 15 is greater than 11, so we can instantly cut our search in half as there is no need to look at the left half of the array. We can then start our new search at 13 and find a new midpoint.

Binary search uses the fact the array is sorted to cut our search list in half every time we make a comparison. That's huge!

Pseudocode

Set a search start and search finish variable
While our search area is valid (i.e. start is less than or equal to our finish)
Set the midpoint index halfway between start and finish
Compare the value at that midpoint index with our search value
If they're equal, great! We can return the midpoint
If the midpoint value is higher than search, then we set our finish index to be the index before our midpoint
If the midpoint value is lower than search, then we set our start index to be the value after our midpoint
If the value isn't there, our search area will eventually become invalid, and we'll return false

Iterative Ruby Code

Solving this iteratively, the code then looks something like this:

def binarySearch(array, search)
  start = 0
  finish = (array.length) - 1

  while start <= finish
    midpoint = (start + finish) / 2
    if array[midpoint] == search
      return midpoint
    elsif array[midpoint] > search
      finish = midpoint - 1
    elsif array[midpoint] < search
      start = midpoint + 1
    end
  end
  return false
end

Recursive Ruby Code

We can also write this recursively, using the same logic. I think it's a bit cleaner, but it does use more memory and we'll need to pass in our start/finish variables as arguments:

def binarySearchRecursive(array, search, start, finish)
  if finish < start
    return false
  end
  midpoint = (start + finish) / 2
  if array[midpoint] == search
    return midpoint
  elsif array[midpoint] > search
    binarySearchRecursive(array, search, start, midpoint - 1)
  elsif array[midpoint] < search
    binarySearchRecursive(array, search, midpoint + 1, finish)
  end
end

And that's binary search! Hope you found this useful and/or interesting, and it saves you some time next time you need to find a needle in a 100M strong haystack...

Forem: Sam Gorick

Binary Search: Speed up your searches!

Pseudocode

Iterative Ruby Code

Recursive Ruby Code