New answers tagged

2

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$ ...


1

The value that you've got is the number of searches required in the worst case by binary search. Each function call is responsible for only 1 search. And your recurrence relation justifies that. So the recurrence relation you wrote is for the number of searches. Indeed we require $\log n +1$ searches if it's a worst case. Take any $n$, say $n=7,8$, and try ...


2

Here is a cleaner and better way to solve the problem. # Return the smallest index where the element is bigger than `A[start_index]`. # If `len(A)` is returned, no element is bigger than `A[start_index]`. def next_bigger_element(start_index, A): lo, hi = start_index, len(A) while lo + 1 < hi: mid = (lo + hi) // 2 if A[mid] == A[...


2

Let's denote the indices by $l,h,m$. If $l \leq h$ and $h-l$ is even then $m = \frac{l+h}{2}$ and so in the following iteration, the new values $l',h'$ will either be $\frac{l+h}{2}+1,h$ or $l,\frac{l+h}{2}-1$. In the first case $$ l'-h' = \frac{l-h}{2}+1 \leq 1, $$ and in the second case $$ l'-h' = \frac{l-h}{2}+1 \leq 1. $$ If $l \leq h$ and $h-l$ is odd ...


Top 50 recent answers are included