1 a. What is the largest number of key comparisons made by binary search in sear

Question

1 a. What is the largest number of key comparisons made by binary search in searching for a key in the following array?

3

b. List all the keys of this array that will require the largest number of key comparisons when searched for by the binary search?

c Find the average number of key comparisons made by binary search in a successful search in this array.

(Assume that each key is searched for with the same probability.)

d. Find the average number of key comparisons made by binary search in an unsuccessful search in this array.

(Assume that searches for keys in each of the 14 intervals formed by the array's element are equally likely )

3

Explanation / Answer

1.a. The worst case to find a key in binary search would be it's extream end element. in this case it is either 3 or 98. Let us consider target search element as 98. First Binary search(BS) alog will go to '55' to and compare it with '98', then it will visit 81, then '93' then '98'(element foiund). So, Maximum number of searches would be 4.

b. To find '98' it needs largest number of comparisions
  List is: 55, 81, 93, 98.

c. average number of comparisios will be log n to the base 2. where n is number of elements in the given array. In this case n = 13. So, Average number of comparisions would be log 13 to the base 2.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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