edited by
425 views
0 votes
0 votes
Let $A=(a_1, a_2, \dots , a_n)$ be an array of $n$ distinct numbers. The array may not be sorted. The $\text{first}$ element $a_1$ is said to be a $\text{blip}$ if $a_1 > a_2$. Similarly, the $\text{last}$ element $a_n$ is said to be a $\text{blip}$ if $a_n>a_{n-1}$. Among the remaining elements, an element $a_i$ is said to be $\text{blip}$ if $a_i > a_{i-1}$ and $a_i>a_{i+1}$ where $ i \in \{2, 3, \dots , n-1\}$. Design an $O(\log n)$ time algorithm for finding a $\text{blip}$ in $A$. Justify the complexity of your algorithm.
edited by

Please log in or register to answer this question.

Related questions