Finding the maximum of a bitonic sequence

Question

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > \dots > B[n].$$

It is noted that the index $i^*$ is not given as part of the input.

The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.

I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions

Answer 1

The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.

The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.

The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.

Answer 2

A sequence satisfying your constraint is known as bitonic. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing or monotone decreasing then increasing). You can find the index $i^*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^*$ as follows:

• If $B[i-1] < B[i] > B[i+1]$, then $i = i^*$.
• If $B[i-1] < B[i] < B[i+1]$, then $i < i^*$.
• If $B[i-1] > B[i] > B[i+1]$, then $i > i^*$.

I'll leave you to handle the corner cases $i = 1$ and $i = n$.