Whats your Favourite Algorithm?

Whether you've studied a computer science related subject or not, complex algorithms can seem quite daunting. You know, the ones you occasionally get asked and have to learn before going into an interview! It might feel like you only really learn these for an interview, but when you start to dig deeper, they can actually be a lot of fun.

Without a doubt my favourite algorithm has to be the binary search. It allows you to efficiently find a number in a sorted array. As an example, let’s imagine the following sorted array of integers.

If I needed to find the number 89 in this array, I could always loop through each value until I found the value I was looking for. The problem is that as the size of the array grows, so does the amount of time it takes to find the value in the array!

This is a perfect opportunity to use the binary search algorithm. A binary search finds the middle value in the array and then determines if the value we are searching for is higher or lower than the middle number in the array. It then does this repeatedly until it finds the value it is looking for. For example, in the array above, the middle value is 10. We know that 89 is greater than 10, which means we can split the array and discard anything lower than 10. We’ve managed to cut the amount of data that we need to search through by half - nice! Our array now looks like the image below.

Using the algorithm above, we can continue to find the middle number and discard values that are greater or less than the one we are looking for. The binary search is a simple, clever way of finding a value regardless of the size of the array.

Taking the above logic and translating it directly to code now becomes easy. Let’s have a look at the code sample below.

In the code above, you can see a function entitled binarySearch. There are a number of steps taking place:

• - The code tries to get the middle value in the array
• - It then determines if the value in the middle of the array is higher or lower than the one we are looking for
• - If it is neither of these values but is actually equal, we can return the middle value, since we have found the value we are looking for!

Simples right!? Well, almost. The eagle eyed among you will notice that this method will only run once and not continually run until it finds the value. You may get lucky and find the middle value on your first run, but it’s pretty unlikely!

We need to tweak this code a little bit more to get it to work as expected. Let's turn the code above into a recursive function.

The code above isn’t very different from our first example, but it is recursive and will continue to call itself until it finds the value in the middle. That’s it!

This example is written in JavaScript, but this algorithm can be applied to any language. There are loads of great algorithms and data structures out there that are worth learning about. I realise that you probably won't come across most of them in your day job - but it’s still cool to understand the science behind them. If you’d like to learn more about algorithms, there are lots of free resources online. I recommend checking out the following videos on Youtube by MIT and this PDF by Princeton University.

What is your favourite algorithm?