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