The next questions refer to binary search used in the rank method in class Binar

Question

The next questions refer to binary search used in the rank method in class BinarySearchST (p. 381). Assume integer keys with sorted keys array: int[] keys = {10,20,30,40,50,60,70}; So initially in rank lo = 0 and hi = 6.

public int rank(Key key)
{
int lo = 0, hi = N-1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) hi = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;

Question 1: For binary search for 30 in the keys array, what is the final value of lo?

Question 2: For binary search for 30 in the keys array, what is the final value of hi?

Question 3: For binary search for 5 in the keys array, what is the final value of lo?

Question 4: For binary search for 5 in the keys array, what is the final value of hi?

Question 5: For binary search for 15 in the keys array, what is the final value of lo?

Question 6: For binary search for 15 in the keys array, what is the final value of hi?

Question 7: For binary search for 25 in the keys array, what is the final value of lo?

Question 8: For binary search for 25 in the keys array, what is the final value of hi?

Question 9: For binary search for 65 in the keys array, what is the final value of lo?

Question 10: For binary search for 65 in the keys array, what is the final value of hi?

Explanation / Answer

Question 1: For binary search for 30 in the keys array, what is the final value of lo? answer is 2
Question 2: For binary search for 30 in the keys array, what is the final value of hi? answer is 2
Question 3: For binary search for 5 in the keys array, what is the final value of lo? answer is 0 because key is not in array
Question 4: For binary search for 5 in the keys array, what is the final value of hi? answer is 6 because key is not in array
Question 5: For binary search for 15 in the keys array, what is the final value of lo? answer is 0 because key is not in array
Question 6: For binary search for 15 in the keys array, what is the final value of hi? answer is 6 because key is not in array
Question 7: For binary search for 25 in the keys array, what is the final value of lo? answer is 0 because key is not in array
Question 8: For binary search for 25 in the keys array, what is the final value of hi?answer is 6 because key is not in array
Question 9: For binary search for 65 in the keys array, what is the final value of lo? answer is 0 because key is not in array
Question 10: For binary search for 65 in the keys array, what is the final value of hi?answer is 6 because key is not in array

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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