Given a bitonic sequence $a_1, a_2, \ldots, a_n$ , calculate the median in $O(\log n)$ 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.
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).