Hello everyone! I need a help in these questions please. 1-Suppose you are given

Question

Hello everyone! I need a help in these questions please.

1-Suppose you are given the array A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], and you then perform the binary search algorithm given in this chapter to find the number 8. Which numbers in the array A are compared against the number 8?

2- Draw the binary search trees of minimum and maximum heights that store all the integers in the range from 1 to 7, inclusive.

3- A certain Professor Amongus claims that the order in which a fixed set of elements is inserted into a binary search tree does not matter—the same tree results every time. Give a small example that proves Professor Amongus wrong.

Explanation / Answer

Answer - 01

Initially lower bound (lb) is 1 and upper bound (ub) is 12

then mid = (lb + ub)/2 = (13 / 2) = 6 and 8 should be compared with 6

As 6 is lesser than 8 , lb is changed to (mid + 1) that is lb = 7, ub remains unchanged
and then mid = (lb + ub)/2 = 9 and 8 should be compared with 9

Here, 9 is greater than 8, thus lb remains same and ub changes to (mid - 1) = 8
and newly computed value of mid = (lb + ub)/2 = (7 + 8)/2 = 7 and 8 should be compared with 7

Here, 7 is lesser than 8, thus ub remains same and lb changes to (mid + 1) = 8 and then newly computed
value of mid = (lb + ub)/2 = (8 + 8)/2 = 8 and 8 is compared with 8 and then match is found

Therefore, following numbers are compared with 8 : 6, 9, 7 and 8

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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