Searching an element in a 2D sorted array I had to write a code (as an exercise) that receives a 2D row wise and col wise sorted array and an element, and return true is the element exists in the array.

The first thing that came to mind when i heard "sorted" is binary search, but than i realized that the last element in each row isn't necessarily smaller than the first one in the next line.

So, i figured out that the best complexity will be O(n), and wrote the following code:

 public static boolean findN(int[][] a, int x) {
        if (a.length == 0 || a[0].length == 0 || x &gt; a[a.length - 1][a[0].length - 1] || x &lt; a[0][0]) {
            return false;
        }
        int LastRow = a.length - 1, Lastcol = a[0].length - 1, row = 0, col = 0;

        while (row &lt;= LastRow) {
            if (a[row][col] == x) {
                return true;
            } else if (col &lt; Lastcol) {
                col++;
            } else {
                col = 0;
                row++;
            }
        }
        return false;
    }



  
    array example:  
  


arr = {{1,2,7,30},  
      {2,4,18,50},  
      {3,6,19,90},  
      {4,7,20,91}}



After realizing that the best complexity will be O(n), I googled this problem  so I'm almost certain that I'm right (although some people are claiming that they can do it in O(log(n))), but am I really?
Any other thoughts and improvements are welcomed, thank you all in advance!
Your function does a linear search over all elements of the nested array, until the given number is found, or all elements have been visited. The complexity is \$ O(mn) \$ for an \$ m \$-by-\$n \$ matrix. For a square \$ n \$-by-\$n \$ matrix that makes \$ O(n^2) \$, and not \$ O(n) \$ as you claimed.

This can be improved, but let's first do a

Review of your current implementation

The Java naming convention for variables is “lower camel case,” e.g. lastRow, lastCol instead of LastRow, LastCol.

The while-loop is a nested loop over all rows and columns in disguise, and can be more clearly written as nested for-loops:

int numRows = a.length;
int numCols = a[0].length;

for (int row = 0; row &lt; numRows; row++) {
    for (int col = 0; col &lt; numCols; col++) {
        if (a[row][col] == x) {
            return true;
        }
    }
}


This also restricts the scope of row and col to the minimum needed.

A better algorithm

Your implementation does not take advantage of the fact that the numbers are sorted in each row and in each column. A better algorithm is described in Search in a row wise and column wise sorted matrix on GeeksForGeeks:


Start with top right element.
Loop: compare this element e with x


if e = x, then return position of e, since we found x in the given matrix.
if e > x then move left to check elements smaller than e (if out of bound of matrix, then break and return false)
if e &lt; x then move below to check elements greater than e (if out of bound of matrix, then break and return false)

repeat until you find the element, or return false


I do not want to deprive you of the satisfaction of implementing it yourself. Just note that any element is now found after at most \$ m+n \$ steps, so the complexity is reduced from \$ O(mn) \$ to \$ O(m+n) \$ for an \$ m \$-by-\$n \$ matrix.