# 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.length == 0 || x > a[a.length - 1][a.length - 1] || x < a) {
return false;
}
int LastRow = a.length - 1, Lastcol = a.length - 1, row = 0, col = 0;

while (row <= LastRow) {
if (a[row][col] == x) {
return true;
} else if (col < 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!
• Find first row that has first element <= X. Find last row that has last element >= X. Execute binary search for rows in between. – TorbenPutkonen Jan 3 at 15:46
• Lat's take X=17. First row that has first element <=17: , last row that has last element >=17: . If ill run binary search for all of this rows the complexity will be O(nlogn). – RedYoel Jan 3 at 18:44
• Your array example is misleading: The third column 7, 18, 16, 17 is not increasing. – Martin R Jan 3 at 20:09
• Edited, same for 18 now. – RedYoel Jan 3 at 20:32

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.length;

for (int row = 0; row < numRows; row++) {
for (int col = 0; col < 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:

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.