Question

Do a trace on the binarySearch method below: variable key holds the value 17, and

variable list is a reference to an array with these values {9, 20, 23, 28, 33, 38, 42, 48, 54, 61,73}.

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

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]
17	0	10	true	5	false	true

    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

Answer 1

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