Suppose that that we have an array called list initialized as follows: int[] lis

Question

Suppose that that we have an array called list initialized as follows:
int[] list = {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103};
This would construct the following array:
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| -2 | 8 | 13 | 22 | 25 | 25 | 38 | 42 | 51 | 103 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Note that the method calls below is of the form:
binarySearch(int[] a, int low, int high, int target)
Write the complete program and
a) What values would low, high and mid take on for the following call:
binarySearch(list,0, 9, 103)
and what value would be returned?

b) What values would low, high and mid take on for the following call:
binarySearch(list, 2, 8, 30)
and what value would be returned?
This should be the output on the following:
a)
The variables would take on the following sequence of values:
low high mid
-------------------
0 9 4
5 9 7
8 9 8
9 9 9
and would return the value 9.
b)
The variables would take on the following sequence of values:
low high mid
-------------------
2 8 5
6 8 7
6 6 6
6 5 -
and would return the value -1.

Explanation / Answer

a) 0 9 4

low=0
high=9
mid=(low+high)/2=(0+9)/2=4
the returned value is 9, and that is the index of 103.

b) 2 8 5
low=2
high=8
mid=(low+high)/2=(2+8)/2=5
the returned value is -1, because there is no value 30 in the array.
-----------------------------------------
So for every searched element that is not in the array the returned value is -1, and if it is in the array the returned value is the index of that element.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.