I claim all $n=2^k-1$ works. The base case, $k=1$, is clear. Let $f(n)$ be the minimum number of steps for $n$. It suffices to show $f(2n+1)\le f(n)+3(n+1)$. Label the grid $(i,j)$ where $0\le i,j\le 2n$. Let $f(i,j)$ be the number written on row $i$ and col $j$. Bert first asks $f(n,j)$ for $0\le j\le 2n$. Let $k$ be the index that satisfies the number on $f(n,k)=\min_{0\le j\le 2n} f(n,j)$, then check whether $f(n-1,k)<f(n,k)$. Assume $1$ is not on row $n$, or we are done. If $f(n-1,k)<f(n,k)$ then $1$ must lie between rows $0$ to $n-1$. This is because if I have a process of filling the numbers in increasing order, the set of squares with a number filled is continuous by the problem condition. It crosses row $n$ at the first time when filling $f(n,k)$, and it goes from $(n+1,k)$ or $(n-1,k)$ to $(n,k)$. WLOG $f(n-1,k)<f(n,k)$. Now check $f(0,n), \cdots, f(n-1,n)$. If $f(j,n) > f(n-1,k)$ for all $0\le j\le n-1$ then $1$ is in the square $(i,j)_{0\le i,j\le n-1}$. Otherwise, if $j$ satisfies $f(j,n)=\min_{0\le t\le n-1} f(t,n)$ then check $f(j,n-1)$. We can reduce the problem from $(2n+1)\times (2n+1)$ to $n\times n$ in $2n+1 + 1 + n + 1 = 3n+3$ moves. The conclusion follows.

(1) It is a lot harder to prove if the answer is no compared to the answer being yes. (2) Filling up the grid in increasing order and D&C are standard ideas. (3) This basically asks for a better algorithm for CAMO 22/4

I claim all $n=2^k-1$ works. The base case, $k=1$, is clear. Let $f(n)$ be the minimum number of steps for $n$. It suffices to show $f(2n+1)\le f(n)+3(n+1)$. Label the grid $(i,j)$ where $0\le i,j\le 2n$. Let $f(i,j)$ be the number written on row $i$ and col $j$. Bert first asks $f(n,j)$ for $0\le j\le 2n$. Let $k$ be the index that satisfies the number on $f(n,k)=\min_{0\le j\le 2n} f(n,j)$, then check whether $f(n-1,k)<f(n,k)$. Assume $1$ is not on row $n$, or we are done. If $f(n-1,k)<f(n,k)$ then $1$ must lie between rows $0$ to $n-1$. This is because if I have a process of filling the numbers in increasing order, the set of squares with a number filled is continuous by the problem condition. It crosses row $n$ at the first time when filling $f(n,k)$, and it goes from $(n+1,k)$ or $(n-1,k)$ to $(n,k)$. WLOG $f(n-1,k)<f(n,k)$. Now check $f(0,n), \cdots, f(n-1,n)$. If $f(j,n) > f(n-1,k)$ for all $0\le j\le n-1$ then $1$ is in the square $(i,j)_{0\le i,j\le n-1}$. Otherwise, if $j$ satisfies $f(j,n)=\min_{0\le t\le n-1} f(t,n)$ then check $f(j,n-1)$. We can reduce the problem from $(2n+1)\times (2n+1)$ to $n\times n$ in $2n+1 + 1 + n + 1 = 3n+3$ moves. The conclusion follows.

(1) It is a lot harder to prove if the answer is no compared to the answer being yes. (2) Filling up the grid in increasing order and D&C are standard ideas. (3) This basically asks for an optimal algorithm for CAMO 22/4