This is the simplest of searches. Every element of the array is compared to the goal one by one. The first occurrence of a match returns the index, and if you go through the whole array -1 is returned.
*1 9 11 13 4 13 10 Goal=11 | First we compare the first element with the goal. (I am using a * to be a place holder). Since it does not match we move on. |
1 *9 11 13 4 13 10 Goal=11 | 9 does not match so we move on. |
1 9 *11 13 4 13 10 Goal=11 | We have an 11, so 2 is returned. Notice that if there was not an 11 the search would continue though the whole array. If we we through the whole array then we know the goal is not in it, and then -1 is returned. |
Let's say that the array bing searched is sorted an every element increases in size. Now let's pick an arbitrary point, say the middle element, the high+low/2, and compare it. If it matches, we return the index. However since the array is ordered we know in which section it is in. If the target is larger than the middle element, if it is anywhere in the array it would be the upper half, otherwise the lower. With each comparison half of the array is discarded. We know that our searching is done without finding the goal when hi and lo used to caculate the middle cross each other.
1 9 11 *13 4 13 10 Goal=11 | First we compare the middle element, (0+6)/2=3, with the goal. 11 is less than 13 so the upper half is useless, [0,6] => [0, 3-1] = [0,2]. |
1 *9 11 / / / / Goal=11 | Compare to the new middle element, (0+2)/2=1. 11 is greater than 9 so that lower half is gone, [0,2] => [1+1, 2] = [2,2]. |
/ / *11 / / / / Goal=11 | Compare to the new middle element (2+2)/2=2. 11 is found so 2 is returned. |
In these examples there was the same amount of comparisons for both searches, but your can probably see how much faster the binary search would go with huge arrays. Also the binary search can be implemented both with iteratively, i.e. with loops, and recursively. Try implementing all the searches before you look at the code.
Prev -- Back to Portal -- Next