How To Think Of... Binary Search
Seems like algorithms and data structures are a weak point for many. Some data structures are used extensively in our day to day code (like an array or a hashtable) while algorithms usually remain hidden under the hood. In any case we rarely come any closer than that and although that’s usually not the problem, Google, Microsoft and Amazon interviews rely heavily on them.
Through these posts we’ll try to explore some of them, understand them and hopefully learn something valuable in the process than just memorising them.
Starting with Binary Search. As the name implies binary search is an algorithm for finding an element. In order to use the binary search we need to have an array of elements.
There is however a pre-condition associated with the array. It needs to be sorted. Let’s see why by taking an array with numbers starting from 0 to 9.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Pick a number (Let’s say 5 but keep it secret for now).
Is it 4? (the average of 0 + 9 is ~4)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ^ No.
Is it lower than 4? No.
Since it’s higher than 4 let’s look between 5 and 9 this time.
Is it 7? (the average of 5 + 9 is 7)
[5, 6, 7, 8, 9] ^ No.
Is it lower than 7? Yes.
Since it’s lower than 7, let’s look between 5 and 6 this time.
Is it 6? (the average of 5 + 6 is ~6)
[5, 6] ^ No.
Is it lower than 6? Yes
Since it’s lower than 6, let’s look between 5 and …5 this time.
 ^ Is it 5? (the average of 5 + 5 is 5)
Notice how given an index to start from and an index to end we always take the average to look for the number. That effectively reduces the numbers to look for by a factor of 2 every time.
Also notice how every time that we don’t find the number we reduce the range to look for.
- If the number is lower that the one we guessed we look from the start till the average minus 1.
- If it’s higher we add 1 to the average and look till the end index.
What’s missing is when to stop looking for the number. If you follow the pattern you will notice that at some point the index to start looking from will be be greater than the end index. That’s when you stop.
So you might ask yourself. In an OO language like Java how useful is that? After all it is objects that we are dealing with. For that reason there is the Comparable interface that you need to implement with a single method that returns an int. It’s up to you to decide whether an object ranks lower or higher than an equivalent.
Note: Do you know that Java has a bug up until version 5.0 when it comes to calculating the average?
“Can’t even compute average of two ints” is pretty embarrassing.