Give an algorithm that finds an arbitrary item X in a binary heap using at most roughly 3N/4 comparisons

Question

This question is in the book of Mark Allen Weiss in exerice 10 in chapter 6 about heaps.

Could you please help me to solve this problem?

I was able to find a solution that gives a 3N/4 comparison in most cases, but there is cases where my algorithm do N comparasions.

In my solution, I start from the level before last and I check if I have to go up (if X < minimum of the level) which gives N/2 comparisons, or I have to go down (if X > maximum of the level) which gives 3N/4 comparisons. But when X is between the min and max of the penultimate level I can't decide whether to go up or down which gives N comparisons.

Answer 1

I contacted the author of the manual (Mark Allen Weiss) and he informed me that the solution is in the article titled: The Complexity of Heaps written by Svante Carlsson and Jingsen Chen.