Lower bound on number of comparisons needed to search for a number in a sorted 3-d array
Let's suppose that the array is indexed using $\{1,\ldots,N\}$, and assume for simplicity that $N$ is odd. Divide the cells in the array into three parts:
$$
\begin{align*}
X &amp;= \{ (i,j,k) : i+j+k &lt; 3 \tfrac{N+1}{2}, \} \\
Y &amp;= \{ (i,j,k) : i+j+k = 3 \tfrac{N+1}{2}, \}, \\
Z &amp;= \{ (i,j,k) : i+j+k &gt; 3 \tfrac{N+1}{2}, \}.
\end{align*}
$$
Consider a 3D array $A$ with $A(i,j,k) = -\infty$ for all $(i,j,k) \in X$ and $A(i,j,k) = \infty$ for all $(i,j,k) \in Z$ (you can think of $-\infty,\infty$ as stand-ins for large negative and positive numbers). We claim that any such array is sorted. Indeed, suppose for example that $i_1 &lt; i_2$ and $j,k$ are given. If $i_1 + j + k &lt; 3\frac{N+1}{2}$ then $A(i_1,j,k) = -\infty \leq A(i_2,j,k)$. If $i_1 + j + k \geq 3\frac{N+1}{2}$ then $A(i_1,j,k) \leq \infty = A(i_2,j,k)$.

It follows that you cannot rule out that a finite number is in $A$ without checking all entries in $Y$ (formally this can be proved using an adversary argument). The number of entries in $Y$ is at least $N^3 / (3N-2) = \Omega(N^2)$.

The same idea extends to give a lower bound of $N^{d-1}/d$ in the $d$-dimensional case.