## Find an element in a matrix whose rows and columns are sorted

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

My initial thoughts:
We are kind-of doing a 2D binary search here. Each time we find the center of the matrix. If that is the element we are looking for, then return it. Notice that the center divide the matrix into four parts: upper-left, upper-right, bottom-left and bottom-right. If the element we are looking for is less than the center, then it cannot be in the bottom-right part, where every elements are even greater than the center. If the element we are searching is greater than the center, then it cannot be in the upper-left part. Hence, each time we approximately eliminate $\frac{1}{4}$ of the entire matrix. Therefore we have the recursion: $T(n)=3T(n/4)+O(1)$, whose solution is $O(n)=n^{0.75}$.

My initial codes:

	public static Pair<Integer> findInMatrix(int[][] data, int rowLow,
int rowHigh, int colLow, int colHigh, int element) {
if (rowLow > rowHigh || colLow > colHigh)
return null;
int rowMid = (rowLow + rowHigh) / 2;
int colMid = (colLow + colHigh) / 2;
int mid = data[rowMid][colMid];
if (mid == element)
return new Pair<Integer>(rowMid, colMid);
else if (element < mid) {
Pair<Integer> topLeft = findInMatrix(data, rowLow, rowMid - 1,
colLow, colMid - 1, element);
if (topLeft == null) {
Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
colMid, colHigh, element);
if (topRight == null) {
Pair<Integer> bottomLeft = findInMatrix(data, rowMid,
rowHigh, colLow, colMid - 1, element);
return bottomLeft;
} else
} else
} else { // element > mid
Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
colMid + 1, colHigh, element);
if (topRight == null) {
Pair<Integer> bottomLeft = findInMatrix(data, rowMid + 1,
rowHigh, colLow, colMid, element);
if (bottomLeft == null) {
Pair<Integer> bottomRight = findInMatrix(data, rowMid,
rowHigh, colMid + 1, colHigh, element);
return bottomRight;
} else
return bottomLeft;
} else
}
}

Solution:
This algorithm works by elimination. Every move to the left (–col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.
public static Pair<Integer> FindElem(int[][] mat, int elem, int M, int N) {
int row = 0;
int col = N - 1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return new Pair<Integer>(row, col);
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}
return null;
}

Comments: Brilliant. Time complexity $O(m+n)$.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5bcfc3b60ee40', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5bcfc3b60ee84',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5bcfc3b60ee88',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related