Class Exercise:  Binary Search

                      
Objective: develop an algorithm to "divide and conquer" or apply a method
   of halving to implement what is termed a binary search. Chapter 7 of
   our text provides a detailed description of this process.
1. An array named list is to have nine components initialized with values: 
   11, 14, 18, 23, 29, 36, 44, 53, 63
         

2. Depict this list as a collection of cells containing the array values
   given in number 1, and with labels to indicate index values (0 ... 8).




3. Identify index values associated with the cells containing 11 (first) and
   63 (last) list values.


4. Compute "mid", the index value for the middle index value as 
   (first + last) / 2.


5. Identify the list value pointed to by mid.



6. Search for the list value 36:  start by comparing 36 to the 
   value pointed to by mid and assign true to the boolean variable 
   named found if they match; otherwise found should remain false.
   What would be the value of found after comparing list[mid] to 36?


7. Should found be false, create a trace table to illustrate successive 
   iterations and corresponding values of first, last, mid, last[mid], found
   and list[mid] compared with the search argument 36.  Note that after the 
   comparison of the search argument(36) to list[mid], the list is to be 
   "halved" by adjusting first to mid+1 or last to mid-1 to find the next mid.

   iteration  first  last  mid  list[mid]  found  list[mid]:36
   ---------  -----  ----  ---  ---------  -----  ------------
       1        0      8    4      29      false   less than   

       2        0

       3
       .
       .
       .

8. Prepare another trace table to show the flow for a search
   argument that is not in the list (e.g. 15)

   iteration  first  last  mid  list[mid]  found  list[mid]:15
   ---------  -----  ----  ---  ---------  -----  ------------
       1        0      8    4      29      false  greater than

       2

       3
       .
       .
       .

   Note: the process should continue while first <= last && !found