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:
Array of integers, named num, arranged in
"ascending order"!!!
10 
15 
24 
36 
45 
55 
64 
73 
90 
98 
num[0] 
num[1] 
num[2] 
num[3] 
num[4] 
num[5] 
num[6] 
num[7] 
num[8] 
num[9] 
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
}
