Find a value in a sorted 2D array

A sorted 2D array has rows and columns that contain increasing values.

For example, find 85 in the following sorted 2D array.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

The general strategy is to eliminate rows and columns by comparing the target value to corner points.

Let's look at the right-most element in the first row. This element is the largest element in the row since it is sorted. In the example, 85 is greater than 80 so we know that it cannot be in this row; thus, we can effectively eliminate the first row.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

At the same time, we can see if the last column can be eliminated by checking if the target value against the aforementioned element in the context of the column. The top-most element in a column is the smallest since it is sorted. Hence, if the target value is less than the top-most element, we can eliminate the column. In this case, it is not because 85 is not less than 80, so we keep the last column.

Now, examine the bottom-most element in the last column. 85 is less than 110 so we must save the last column and last row.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

How about the left-most element in the last row. 85 is greater than 50 so we cannot remove the last row. However, we can remove the first column since 85 is greater than 50.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Now, the top-most element in the new first column... 85 is not less than 55 so we cannot remove this column. We cannot remove the row either because again, 85 not less than 55.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Look at the right-most element in the first row. 85 is not greater than 95 so cannot strike this row, but it is less than 85 so we can remove the column.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Next, check the bottom-most element in the last column, 90. We cannot cross the row nor column because 85 is not greater than 90.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Examine the left-most in the last row. For the row, 85 is not less than 70. For the column, it is greater than 70; thus, we can eliminate the column.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

When we have 1 row or column left, we can perform a binary search for the value.