We simply think that we can do a binary search in each row or each column. In this case, the time complexity is O(mlog(n)). This is simple.
But why is this problem is designed? For binary search problems, the 1D array is sufficient. There is some other logic to solve this problem than the above binary search approach.
This is quite tricky. We can do a search in a 2D sorted array with a time complexity of O(m+n) where m is the number of rows and n is the number of columns. I didn’t directly think of this new logic which I am going to explain.
This 2D sorted array is the array where each row is sorted and each column is sorted.
For better search optimization we can start searching from the bottom left corner that is the last row and first column element.
If that element is matching with the target, we can simply return there.
If not matching and the target element is greater than the corresponding element, we can increment the column and proceed. Here we are incrementing the column because the next element in the column is of greater or equal value than the previous element.
If the target element is lesser than the corresponding element, we can decrement the row and proceed. Here we are decrementing the row because the previous element is of equal or lesser value than the corresponding element.
With the above logic, we can achieve the search functionality in O(m+n).
C Code segment:
int row = matrixSize-1;
int col = 0;
/* starting from bottom left , going up or right */
while (row >= 0 && col < matrixColSize)
{
/ check if matching element /
if (matrix[row][col] == target)
return 1;
/ if end of element is greater , search in upper rows /
if (matrix[row][col] > target)
row — ;
else / if (matrix[row][col] < target) else case /
/ if the [row][col] element is lesser, search in next column */
col++;
}
return 0;
Your comments please.
