I was wondering what is the most efficient way to find the a number in an array with the following conditions:
Array $A$ of size $n$ divided into even parts in the size of $k$
- every element in each part is bigger than all the elements in the part before (Lets say in the left)
- every element in each part is smaller then then every elements in the part after it (lets say on the right)
At this moment after trying couple of ways I am under the impression that the only way is $O(n)$
Is it correct?