How many comparisons does it take to find a number in a grid of numbers arranged in an $N \times N$ square

Question

We have an $N \times N$ squares, filled with integer numbers monotonically increasing in "right" and "down" directions.

So from any point, if you move left the number will get bigger, or if you go one step downwards the number would get bigger.

Using induction (preferably) prove we need $2N-1$ comparisons at most, to find out if a given number is in the square or not.

Each comparison will let us know if the number in the square is bigger, smaller or equal to the number we seek.

Answer 1

Intuitive Algorithm assuming matrix is completely monotonic:

1. Search along diagonal starting from (1,1).

1 worst case: exactly N comparisons

2. number will be between two kitty corner numbers on the diagonal (i,i) and (i+1, i+1). So, start from (i,i+1) and search moving right until you hit (i,N) or you find what you're looking for.
3. start from (i+1,1) and move right until you hit (i+1,i). If you find what you're looking for, you're done. Otherwise, your number isn't on the list.

2/3 Worst case: N-1 comparisons

Therefore, total, 2N-1 comparisons.

If you need to use induction, your base case is a 1X1 matrix - trivial. Then, for the inductive step, inside an N+1 X N+1 matrix, there is an NXN matrix that is also doubly monotonic. Implication follows. Constructive proofs are better than inductive in my opinion.

For the general case, I'll have to work that out.