/**
* Do binary search in this "ordered" matrix
*/
public boolean searchMatrix(int[][] matrix, int target) {
int row_num = matrix.length;
int col_num = matrix[0].length;
int begin = 0, end = row_num * col_num  1;
while(begin <= end){
int mid = (begin + end) / 2;
int mid_value = matrix[mid/col_num][mid%col_num];
if( mid_value == target){
return true;
}else if(mid_value < target){
//Should move a bit further, otherwise dead loop.
begin = mid+1;
}else{
end = mid1;
}
}
return false;
}
Binary search on an ordered matrix


I thought the same, but wouldn't it be faster to first skip all the rows whose last element is smaller than the target?
Semi pseudo:
for (int i = 0; i < numOfRows; i++) { if (matrix[i, numOfColumns  1] < x) continue; else return binarySearch(remainderOfMatrix); }
, or would the binary over the entire matrix as an array still be faster on its own?

Why you might want to consider some other solution instead of this 

row_num * col_num
might cause overflow. 
Also,
/
and%
are expensive operations. 
For more problems with this solution, Refer to the comments in this solution : https://leetcode.com/discuss/10735/
Great solution, but
I think there are better solutions than just treating it as a list.


By looking for a suitable row first and then doing a binary search, you end up with a runtime complexity of O( rows + log( cols ) ); whereas, if you treat the whole search space as a single array, you end up with a runtime complexity of O( log( rows * cols ) ). So, to put it in context, imagine you have a 2dimensional array consisting of 1million rows and 10columns, then you'll end up with the following:
1000000 + log( 10 ) = 1000001
log( 1000000 * 10 ) = 7
Your approach will have 1000001 operations, whereas the latter will have only 7.

@aroux to look for a suitable row, you can also use binary search, which takes
O(log row)
. These 2 methods have the same running time. But treating 2d array as a 1d array may cause overflow.


bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.size()==0) return false; int m=matrix.size(); int n=matrix[0].size(); int row=0,column=n1; while(row<m && column>=0) { if(matrix[row][column]==target) return true; else if(matrix[row][column] >target) column; else row++; } return false; } Simple Solution Accepted in one Go