Searching a value in a "piecewise" ordered array If we have an array $A$ of length $N$, which is partitioned into $\sqrt{N}$ adjacent subarrays $A(i)$, each of which is monotonically ordered from $\min(i)$ to $\max(i)$ (it is known what places have those bounds in A for each subarray), with the following conditions:

min(i) &lt; min(i+1),
max(i) &lt; max(i+1),
min(i+1) &lt; max(i),
If subarrays A(i) and A(i+1) both have the j-th element, then A(i,j) &lt; A(i+1,j),
The number of elements in subarray A(i) is strictly increasing with i


Would it be possible to search an element in the array $A$, in time $O((\log N)^k)$, for a positive $k$?  If yes how?

If not, what kind of minimal additional conditions would allow that?

Edit. The subarrays are not necessarily of equal length.
They are strictly increasing. The above stated conditions are always guaranteed.

What I have tried so far is to binary search them separately, but that is obviously going to be very inefficient. 

[Note that this question has obviously nothing to do with the search of the min of max value in the array. And I am not interested in sorting the array. Just the mere search.]
It should be possible to do this with $O(\sqrt{N})$ comparisons, saving an $O(\log N)$ factor over the straightforward "binary search each subarray".

The last condition, that the lengths of the subarrays strictly increases, makes things messy.  The analysis of $M$ subarrays, each of length $M$, is easier and it should be straightforward to extend the method to increasing-length subarrays.
Note that $\log M = O(\log N)$.

Also complicating things are the strict inequalities; it is easier to work with non-strict inequalities (which are also more general).

Finally, the conditions ensure that in subarray $A(i)$, the first element $A(i,1)$ is the minimum value and the last element $A(i,M)$ is the maximum value, so there is no need to deal with these elements explicitly.  This yields the simplified problem


there are $M$ subarrays of equal length $M$, and
for all $i,j$


[monotonicity across subarrays] $A(i,j) \le A(i+1,j)$,
[adjacent subarrays overlap] $A(i+1,1) \le A(i,M)$, and
[monotonicity within subarrays] $A(i,j) \le A(i,j+1)$.



If there is $u$ such that $A(u,1) \le n &lt; A(u+1,1)$,
then only the first $u$ subarrays need to be considered,
and similarly for $v$ such that $A(v-1,M) &lt; n \le A(v,M)$ focuses attention on the last $v$ subarrays; together their intersection defines a set of subarrays that must contain $n$.  The rest of the subarrays can be ignored.
This preprocessing can be done in $O(\log N)$ steps.

Then $A(i,1) \le n \le A(i,M)$ is guaranteed for each remaining $i$ in the range $M-v+1$ to $u$, otherwise $n$ is not in the array.  For the remainder, suppose that the preprocessing did nothing, so $u=v=M$ (this is the worst case). Run binary search on the middle subarray $w=\lfloor M/2\rfloor$; this determines that $A(w,j) &lt; n &lt; A(w,j+1)$; (if equality holds then $n$ has been found).

By monotonicity across subarrays, $A(i,j) \le A(w,j) &lt; n$ for all $i \le w$ and similarly $n &lt; A(w,j+1) \le A(i,j+1)$ for all $i \ge w$.

Now we need to recursively search about half of the remaining elements, considering the two rectangular blocks $A(1,j+1)..A(w-1,M)$ and $A(w+1,1)..A(M,j)$ in turn.  There are $M$ calls to check a block, but successive calls receive exponentially smaller blocks to work with.  Amortising the work across calls, the total work is $O(\sqrt{N})$ steps as each leaf of the search tree only does a constant amount of work.  More precisely this relates to solving the recurrence $f(n) = 2f(n/4) + \log n$ for which $f(n) \in O(\sqrt{n})$.

So overall, $O(\sqrt{N})$ steps suffice.

Note that the overlap of adjacent subarrays may be of use when extending to increasing-length subarrays, or in improving the algorithm, but isn't used here.

As far as I can tell, $\Omega(\sqrt{N})$ is also a lower bound.  A handwaving argument is that in the worst case, when all the values are close except for a single missing value, that value could be hidden in any of the rows and each row must be examined at least once.