If we have a sorted array we do not need to check every element to find out if the array contains the element we are looking for. We can try to narrow down the array, making the area we check smaller each time. If we can divide the array in half each time we search it, we have improved the speed of our search exponentially.

When trying to guess a number you might ask, "Is it smaller than 5000 ?" If you receive a positive response you might ask, "Is it larger than 0 ?" If you again receive a positive response, what would you ask? You should ask, "Is it larger than 2500 ?". What ever response you get, you will have reduced the posible number by half. If you received a negative response you should ask, "Is it larger than 1250 ?". By continuing in this way you reduce the possiblities by half each time. You will quickly close in on the correct number. Since you are dividing the possible numbers by 2 each time, this is called a binary search. Since you are cutting the problem down in size each time, this is also a type of divide and conquer algorithm.

A method to do a binary search on a given array can be written recursively. The base case would be an array of size 1. All larger arrays can be solved by passing one half of the array into the method recursively a second time, and so on. The choice of which half to send back into the method will be made by checking if the number to-be-found is larger than the element in the middle of the array. If it is larger, then send the upper half of the array, if it is not larger, then, if it is not equal to the middle value, send the lower part of the array back into the method. If it is equal, simple return the middle index.

See also here for more on Divide-and-Conquer Algorithms and sorting.

© Nachum Danzig December 2003