Question

Do a trace on the code below. In the method binarySearch below: variable key holds the value 27, and

variable list is a reference to an array with these values {12, 25, 36, 39, 43, 65, 78, 86, 99, 108, 121}.

public static int binarySearch(int[] list, int key) {

    int lowIndex = 0;

    int highIndex = list.length - 1;

    while (highIndex >= lowIndex) {

      int midIndex = (lowIndex + highIndex) / 2;

      if (key < list[midIndex]){

           highIndex = midIndex - 1;

     }

      else if (key > list[midIndex]){

           lowIndex = midIndex + 1;      

     }

      else if (key == list[midIndex]){

           return midIndex;            

     }

    } // end of while loop

    return -1;

} // end of binary search method

Each row in the table below corresponds to one iteration of the while loop in the method above. You can add or remove rows according to the actual number of iterations. The first row’s information corresponds to the first iteration, and its value has been filled. You need to continue for the following rows.

key	lowIndex	highIndex	highIndex>=lowIndex	midIndex	key==list[midIndex]	key<list[midIndex]
27	0	10	true	5	false	true

Given the key value and array content listed above, what is the return value of the binary search method?

Re-do the code tracing, and this time, the key is changed to 80, as indicated by the table below.

key	lowIndex	highIndex	highIndex>=lowIndex	midIndex	key==list[midIndex]	key<list[midIndex]
80	0	10	true	5	false	false

Answer 1

Given list is {12, 25, 36, 39, 43, 65, 78, 86, 99, 108, 121}

key	lowIndex	highIndex	highIndex>=lowIndex	midIndex	key==list[midIndex]	key<list[midIndex]
27	0	10	true	5	false	true
27	0	4	true	2	false	true
27	0	1	true	0	false	false
27	1	1	true	1	false	false
27	2	1	false

So. key 27 not found in the array

Given list is {12, 25, 36, 39, 43, 65, 78, 86, 99, 108, 121}

key	lowIndex	highIndex	highIndex>=lowIndex	midIndex	key==list[midIndex]	key<list[midIndex]
80	0	10	true	5	false	false
80	6	10	true	8	false	false
80	6	7	true	6	false	true
80	7	7	true	7	false	true
80	8	7	false

So. key 80 also not found in the array