1
$\begingroup$

This is a question in my textbook, it requires me to write an algorithm to find the median of a bitonic sequence in $O(\log n)$, where $n$ is the number of elements (a bitonic sequence is a sequence that is non-increasing first, and then it's non-decreasing after some point). How do I approach this? I feel like it has something to do with the medians of the 2 parts (the non-increasing and non-decreasing parts of the sequence), but I couldn't find a way to solve it from there.

Any help would be much appreciated. Thank you.

$\endgroup$

1 Answer 1

2
$\begingroup$

First you use an algorithm to find the bitonic point, that is the point where the sequence swaps from being non-increasing to non-decreasing. This is possible with this algorithm in $O(\log(n))$. Now you split the sequence apart at this point (virtually, you don't really make any copies since that would cost $O(n)$). You can now use this algorithm to find the median of two sorted sequences in $O(\log(\min(u,v)))$. $u+v = n$ in our case since we split the original sequence.

Beware that you need to adjust the given algorithms since the first one uses the opposite definition of bitonic (first increasing the decreasing) and the second one assumes that both arrays are sorted in the same direction (in our case one is in reverse).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.