find number in array divided into k parts 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?
Choose an arbitrary representative from each part. Using binary search, you can find the two representatives which bracket the given element. You can then look for your given element in the $2k$ elements comprising the two parts that the representatives belong to. This algorithm takes time $O(\log(n/k) + k) = O(\log n + k)$, interpolating between the cases $k=1$ (sorted array, $O(\log n)$) and $k = n$ (unsorted array, $O(n)$).