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 value to the subscript of the last value and dividing by two:  (0 + 9) / 2 = 4    Integer division is being used to arrive at the 4th subscript as the middle.  (The actual mathematical middle would be between the subscripts 4 and 5, but we must work with integer subscripts.) 

• Subscript 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

• Subscript 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

• Subscript 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 lower bound and upper bound subscripts...
// 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;    //count the number of comparisons (optional)

       // To start, find the subscript of the middle position.
       position = ( lowerbound + upperbound) / 2;

       while((array[position] != key) && (lowerbound <= upperbound))
       {
              comparisonCount++;
              if (array[position] > key)               // If the number is > key, ..
             {                                                       // decrease position by one.
                    upperbound = position - 1;   
             }                                                      
             else                                                
            {                                                        // Else, increase position by one.
                   lowerbound = position + 1;     
             }
             position = (lowerbound + upperbound) / 2;
       }
      if (lowerbound < = upperbound)
      {
            cout<< "The number was found in array subscript "<< position<<endl<<endl;
            cout<< "The binary search found the number after " << comparisonCount
                   << " comparisons.\n";             
            // printing the number of comparisons is optional
       }     
       else
             cout<< "Sorry, the number is not in this array.  The binary search made "
                   <<comparisonCount << " comparisons.";
       return;  // you may also consider returning the subscript
}