) Do a trace on the binary search method below: variable
key
holds the value
42, and variable
list
is a reference to an array with these values
{16, 22, 25, 37, 38, 41, 49, 52, 59, 66, 71, 76}.
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 <>
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 needed. The first row’s information corresponds to the first iteration. You need to fill in the first row for the first iteration, then the second row for the second itertation, so on and so forth, until the loop stops and the method finishes.
key
|
lowIndex
|
highIndex
|
highIndex>=lowIndex
|
midIndex
|
key==list[midIndex]
|
key<>
|
42
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
42
|
|
|
|
|
|
|
Given the key value and array content listed above, what is the return value of the binary search method? ______
How does binary search algorithm work?