Binary Search

Sometimes, an elegant algorithm in computer science is processed the
same way a person would perform a task. For example, if you were looking
up a name in a phone book, you wouldn’t start at the very beginning
of the book. You would perhaps start somewhere in the middle, and divide by half
each time until you zeroed in on the target.

Maybe you know that the phone book is alphabetized, and if the name started with a “B,”
then you might start towards the beginning of the book. However, imagine that you didn’t know
how many names there were for each letter, and it’s possible that letters that
start with “A” could take up a majority of the book. Here, you might guess to
open the book up to about the center, and go from there. For the rest of
this post, let us assume we don’t know the distribution of the numbers in an array,
but only that it is sorted.

When you looked up the numbers in the phone book, you are roughly doing a “binary search.”
Here is a table that shows how a computer might process the steps:

Binary search (credit: http://introcs.cs.princeton.edu/java)

Binary search (credit: http://introcs.cs.princeton.edu/java)

If we were to do a “brute-force” method, which is checking each number starting at
the beginning, the process will take on the order of N/2 times on average, where N
is the number elements in the array. If we guess at random until we find the target,
it will also take on the order of N/2 times on average.

However, binary search limits the set that we must search by half each time, so it
will only take on the order of lg N on average. For illustration, if there were 10,000,000
numbers, the brute-force method will take 5,000,000 steps on average, whereas binary search
will take on average 23 steps!

It is worth thinking about efficient algorithms, because even the best hardware will lose
to a great algorithm.

As always, let’s let the code do the talking!

Euclid’s Algorithm

Euclid was a very prolific mathematician, and it is probably a mistake to be surprised that his name resides in yet another algorithm – one used to determine the greatest common divisor. This is commonly known as Euclid’s Algorithm. This algorithm is very simple (only 2 steps), but it can seem subtle at first.

The greatest common divisor (GCD) is the largest number that two integers can divide by. For instance, the greatest common divisor of 16 and 12 is 4. In this post, we consider only nonnegative integers.

Consider the following illustration (left side only – the one labeled “Euclid’s example”), where the two black bars represent the integers for which we seek the greatest common divisor.

Illustration of Euclid’s Algorithm

The black bars are those labeled AB and CD. Suppose we craft the bars so that CF (blue) is in fact the greatest common divisor of AB and CD. Let AB be 10 times the length of CF, and CD be 7 times the length of CF.

Suppose that the length of AB is larger than the length of CD. The trick in the algorithm is that the difference, or d, between AB and CD (AB – CD) will always be greater than the GCD, unless AB = CD (in which case AB or CD is the GCD).

The reason why d will always be greater than the GCD is because both AB and CD must be a factor of GCD, and the difference between AB and CD must be a factor GCD. Therefore, GCD is a factor of d, so d must be greater than or equal to GCD.

The steps to the algorithm are as follows, if AB and CD are the two nonnegative integers we wish to find the GCD for:

Step 1: Let AB be the larger of the two numbers. Then set d = AB – CD

Step 2: If d = 0, then CD is the GCF. If d is not 0, then repeat Step 1 with AB = CD, and CD = d

However, the subtraction method can take many steps if the two values AB and CD are far apart. It has been common to reduce the number of steps by calculating the remainder between AB and CD. The same logic still applies, however, except we remove the many factors of CD in the difference d between the two numbers AB and CD for each loop.

We can now let the code do the talking!