10.2 Binary Search

When the item you are searching for is located in a set of ordered data you can be much more efficient in your search. You can use the approach you would probably use if you were trying to guess somebody's number between 0 and 100. If they tell you higher or lower with each guess you can minimize the number of guesses. Suppose the number they picked was 31. You could start by guessing 50 (the middle). They'll tell you to guess lower. Now you know the number is between 0 and 49. You've eliminated half the possibilities. So now guess 24. Higher. Now the number is between 25 and 49. In two tries we've eliminated 3/4 of the possiblities. Now guess 37. Lower. Between 25 and 37. Now guess 31. Bingo. This is the approach a binary search uses.

Example

We need three variables to keep track of a binary search. We need the bottom index of the range, the middle and the top index. Here is an applet to demonstrate how these variables will be used.

Now let's look at the code to implement this search: 

public static int binSearch(double[] list, double item)
{
   int bottom = 0;
   int top = list.length - 1;
   int middle;
   boolean found = false;
   int location = -1;
   
   while (bottom <= top && !found)
   {
      middle = (bottom + top) / 2;
      if (list[middle] == item)
      {
         found = true;
         location = middle;
      }
      else if (list[middle] < item)
         bottom = middle + 1;
      else
         top = middle - 1;
   }
   return location;
}

Try tracing through the code using the first example. It would get called in a fragment like this:

double[] nums = {5, 9,15,17,28,33,38,39,41,73,83,99};
int index = binSearch(nums, 73);
In our case index would equal 9.