Do a trace on the code below. In the method binarySearch below: variable key hol
ID: 3703095 • Letter: D
Question
Do a trace on the code below. In the method binarySearch below: variable key holds the value 27, and
variable a 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
key
lowIndex
highIndex
midIndex
highIndex>=lowIndex
key==list[midIndex]
key<list[middle]
27
Given the key value and array content listed above, what is the return value of the binary search method? ___
Each row above correspond 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 search key value is set to 80.
How does the binary search work? (use simple words as if to explain to a non-technical person) __________________________________________________________________________________
__________________________________________________________________________________
__________________________________________________________________________________
__________________________________________________________________________________
__________________________________________________________________________________
key
lowIndex
highIndex
midIndex
highIndex>=lowIndex
key==list[midIndex]
key<list[middle]
27
Explanation / Answer
Given the key value and array content listed above, what is the return value of the binary search method?
Ans = -1
because key value is not present in the array.
Each row above correspond 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 search key value is set to 80.
ey
lowIndex
highIndex
midIndex
highIndex>=lowIndex
key==list[midIndex]
key<list[middle]
80
0
10
5
yes
no
no
80
6
10
8
no
no
yes
80
6
7
6
yes
no
no
80
7
7
7
no
no
yes
How Binary Search Works:
binary search works on the sorted list/Array( collection of objects). it works on the divide and conquers approach by repeatedly dividing the search interval in half. let say the object that we have to find is key.
first key object is compared with middle element of the list. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty..
ey
lowIndex
highIndex
midIndex
highIndex>=lowIndex
key==list[midIndex]
key<list[middle]
80
0
10
5
yes
no
no
80
6
10
8
no
no
yes
80
6
7
6
yes
no
no
80
7
7
7
no
no
yes
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.