find number in array divided into k parts
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)$).