3
$\begingroup$

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

|cite|improve this question
$\endgroup$
3
$\begingroup$

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. enter image description here

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.

enter image description here

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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