# Binary search on an ordered matrix

• ``````/**
*  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 = mid-1;
}
}

return false;
}``````

• Same idea. Consider the matrix as a sorted array and apply the normal binary search.

• int mid = (begin + end) / 2;

should be

int mid = begin + (begin + end) / 2;

• should be
int mid = begin + (end - begin) / 2

• yeah, my mistake

• I wonder what's the difference between these two expressions.

• Hi, ztyhlzr. The tricky difference between (begin + end) / 2 and begin + (end - begin) / 2 is that there may be overflow for the former if both begin and end are large but won't be a problem for the latter.

• 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?

• I like when people downvote without explaining why. Sorry for asking a question i guess.

• This post is deleted!

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

1. `row_num * col_num` might cause overflow.

2. Also,`/` and `%` are expensive operations.

3. 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 2-dimensional array consisting of 1-million rows and 10-columns, 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.

• Will not work for input
[[1,2,3,4,5],[3,4,6,11,14],[5,7,9,12,15],[7,9,15,20,22],[9,12,16,25,29]]
11

• @dipenthakkar Your input is invalid.

• Could someone explain what is happening when he does division for the row value and modulus for the column value?

• Cannot pass the test, you missed one line:

``````if (matrix.length == 0 || matrix[0].length == 0) return false;
``````

• `````` 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=n-1;
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``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.