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) {
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] |
17 |
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?
The table is:
key | lowIndex | highIndex | highIndex>=lowIndex | midIndex | key==list[midIndex] | key<list[midIndex] |
17 | 0 | 10 | true | 5 | false | true |
17 | 0 | 4 | true | 2 | false | true |
17 | 0 | 1 | true | 0 | false | false |
17 | 1 | 1 | true | 1 | false | true |
The return value of the binary search method is -1 because highIndex == lowIndex value is true and key == list[midIndex] value if false, so it exists the while loop and after it exists the while loop only one value is returned i.e. -1.
If you have any queries regarding the table/answer comment down below. I will help you out as soon as possible.
Get Answers For Free
Most questions answered within 1 hours.