How To Think Of... Binary Search
/**
* Divide and conquer
*/
public class BinarySearch
{
/*
* Let's start looking from the beginning of the array
* 0 till the last index which is length - 1.
* e.g. an array of size 10 has positions from 0 to 9.
*/
public int indexOf(int[] numbers, int what) {
return this.indexOf(numbers, what, 0, numbers.length - 1);
}
private int indexOf(int[] numbers, int what, int fromIndex, int toIndex)
{
if(fromIndex > toIndex)
return -1;
/*
* Let's take the average by shifting bytes.
* How does that work?
*
* For indexes of 0 to 9 we have 9 >>> 1
* 9 in binary is 1001, therefore
*
* 1001 >>> 1 = 0100
*
* which is equal to 4
* Notice how we are moving each bit 1 position to the right.
* So
* 1 becomes 0
* 0 becomes 1
* 0 becomes 0
* 1 falls off and becomes 0
*/
int average = (fromIndex + toIndex) >>> 1;
int guess = numbers[average];
if(guess == what){
return average;
}
return what < guess?
indexOf(numbers, what, fromIndex, average-1):
indexOf(numbers, what, average+1, toIndex);
}
}
/**
* Let's assert that it works
*/
public class BinarySearchTest
{
public void assertIndexOf(int[] numbers, int what, int index)
{
BinarySearch search = new BinarySearch();
int indexOf = search.indexOf(numbers, what);
Assert.assertEquals(index, indexOf);
}
/**
* Makes the following asserts
* <ul>
* <li> returns -1 on an empty array</li>
* <li> returns the index on an odd elements array</li>
* <li> returns the index on an even elements array</li>
* <li> returns the index on an odd elements array with a direct hit</li>
* <li> returns the index on an odd elements array after 1 division</li>
* <li> returns the index on an even elements array after 1 division</li>
* <li> returns the index on an even elements array after 2 divisions</li>
* <li> returns -1 on a non empty array -ithout the element</li>
* </ul>
*/
@Test
public void indexOf()
{
assertIndexOf(new int[]{}, 0, -1);
assertIndexOf(new int[]{0}, 0, 0);
assertIndexOf(new int[]{0, 1}, 0, 0);
assertIndexOf(new int[]{0, 1}, 1, 1);
assertIndexOf(new int[]{0, 1, 2}, 0, 0);
assertIndexOf(new int[]{0, 1, 2}, 1, 1);
assertIndexOf(new int[]{0, 1, 2}, 2, 2);
assertIndexOf(new int[]{0, 1, 2, 3}, 0, 0);
assertIndexOf(new int[]{0, 1, 2, 3}, 1, 1);
assertIndexOf(new int[]{0, 1, 2, 3}, 2, 2);
assertIndexOf(new int[]{0, 1, 2, 3}, 3, 3);
assertIndexOf(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 10, -1);
}
}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.
[5]
^
Is it 5? (the average of 5 + 5 is 5)
Yes.
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.