Searching an element in a 2D sorted array
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.