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 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. (Assume that each key is searched for with the same probability. ) 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) largest number of comparisons will be : 3 its a general formula . i.e, largest number of key comparisons will be lower bound of lg(n) + 1 where n is the total number of elements. (b) comparison made for searching 1 = 3 comparison made for searching 3 = 2 comparison made for searching 5 = 3 comparison made for searching 7 = 1 comparison made for searching 9 = 3 comparison made for searching 11 = 2 comparison made for searching 13 = 3 so total = 17 so, average = 17 /7 = 2.43 (c) for an unsuccessful search u have to do the largest number of comparisons for each search. so each time u have to do 3 comparisons average = 3

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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