Binary Search

Do you remember playing the game "Guess a Number", where the responses to the statement "I am thinking of a number between 1 and 100" are "Too High", "Too Low", or "You Got It!"?  A strategy that is often used when playing this game is to divide the intervals between the guess and the ends of the range in half.  This strategy helps you to quickly narrow in on the desired number. 

When searching an array, the binary search process utilizes this same concept of splitting intervals in half as a means of finding the "key" value as quickly as possible.

If your array is in order (ascending or descending), you can search for the desired "key" item quickly by using a binary search algorithm (referred to as the "divide and conquer" approach).  

Consider the following array of integers:

We will be searching for the key number 64.  Here is how the binary search will work:

• First, the middle of the array is located by adding the array subscript of the first character to the subscript of the last character and dividing by two:  (0 + 9) / 2 = 4    Integer division is being used to arrive at the element 4 as the middle.  (The actual mathematical middle would be between the elements 4 and 5, but we must work with integer subscripts.) 

• Element 4 holds the number 45, which comes before 64.  We now know that 64 would exist in the portion of the array to the right of 45.  We now find the middle of the right portion of the array by using the same approach:  (5 + 9) / 2 = 7

• Element 7 holds the number 73, which comes after 64, so we now need to find the middle of the portion of the array to the right of 45, but to the left of 73:   (5 + 6) / 2 = 5

• Element 5 holds the number 55, which comes before 64, so we now subdivide again 
  (6 + 6) / 2 = 6   and element 6 holds the number 64.

// function call to the binary search function (listed below)
// for the array shown above
   binarySearch(num, 0, 9, 64);

//Binary Search Function
// Function accepts an array, the subscript range of elements in array ...
// to be searched, and the key number for which we are searching.
// There is nothing returned.
void binarySearch(apvector <int> &array, int lowerbound, int upperbound, int key)
{
       int position;
       int comparisonCount = 1;     //variable used to count the comparisons.

       // calculate the first search position.
       position = ( lowerbound + upperbound) / 2;

       while((array[position] != key) && (lowerbound <= upperbound))
       {
              comparisonCount++;
              if (array[position] > key)               // if the value in the array[position]..
             {                                                       // is greater than the number for …
                    upperbound = position - 1;    // which we are searching, change ..
             }                                                       // upperbound to the position…
             else                                                 // minus one.
            {                                                        // Else, change lowerbound to ..
                   lowerbound = position + 1;     // position plus one.
             }
             position = (lowerbound + upperbound) / 2;
       }
      if (lowerbound < = upperbound)
      {
            cout<< "The binary search found the number after " << comparisonCount
                   << " comparisons.\n";
            cout<< "The number was found in array subscript "<< position<<endl<<endl;     
       }     
       else
             cout<< "Sorry, the number is not in this array.  The binary search made "
                   <<comparisonCount << " comparisons.";
       return;
}