How to do binary search on a path in a binary heap I am trying to solve this question:
Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in time $O(\log(\log n))$.
My solution:
Before the loop, I will create a new linked list and initiate $heap[i]$ to be the first item in the list.
Then, I will run a loop on the heap that will start from index $i$, and in every iteration, it will extract the parent of the item in the index $i$ to a new array and will break after extracting the root of the heap.
Then, I will use binary search on the new array (I know that every parent in the heap is bigger than its children. So the new array is already sorted).
The problem is that the extraction of the parents cost me $O(\log i)$ which can be in the worst-case  $O(\log n)$, and for that reason, my solution can't work.
I will be grateful for any help.
Note that a path from the root to $heap[i]$ is in the sorted order. Moreover, the path length is $O(\log n)$. You just need to do binary search on this path. For that, you need to access the $i^{th}$ ancestor of any node in the heap in $O(1)$ time. Assuming $1$ based indexing, the $1^{st}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{2} \rfloor$ location in the array. The $2^{nd}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{4} \rfloor$ location, and so on. Using it you can easily perform binary search on the path from root to $heap[i]$ in $O(\log \log n)$ time.
Pseudocode:
Assume that we have a min heap. Initialize, start = $1$ and end =  $h = \lfloor \log(i) \rfloor$
BinarySerach (start, end)

mid = (start + end)/2
index of mid = i/(2^(h- mid)) //(h-mid)^th ancestor of i

if (end-start = 1)
    if (heap[index of mid] == x) return &quot;YES&quot;; otherwise &quot;NO&quot;.

if (heap[index of mid] &gt;= x)
   return BinarySearch (start, mid)
else  
   return BinarySearch (mid+1,end)