What is the largest number of key comparisons made by binary search in searching

Question

What is the largest number of key comparisons made by binary search in searching for a key in the following array?
1,3,5,7,9,11,13

according formula(4.4) Cworst=log2(7+1)=??? right?

b)Find the average number of key comparisons made by binary search in a successful search in this particular array. Don't use any formula from the book but instead, find out how many times it takes for each key 1,3,5,7,9,11,13 and take the average.

1/8*1*1+1/8*2*2+1/8*3*4+1/8*4*6???

c)Find the average number of key comparisons made by binary search in an unsuccessful search in this array. Again, don't use any formula from the book but find out how many key comparisons for 0,2,4,6,8,10,12,14 and take the average.

Explanation / Answer

a)

C worst = log2(7+1) = 3

b)

For searching 1,no. of comparisons = 3

For searching 3,no. of comparisons = 2

For searching 5,no. of comparisons = 3

For searching 7,no. of comparisons = 1

For searching 9,no. of comparisons = 3

For searching 11,no. of comparisons = 2

For searching 13,no. of comparisons = 3

Hence C avg = (3+2+3+1+3+2+3)/7 = 17/7 = 2.43

c)

All unsuccessful comparisons take worst time which is 3

Hence C avg = 3

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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