Searching a value in a "piecewise" ordered array
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.