SOmebody explain this approach. It works but i dont know why!


#1

int Solution::searchMatrix(vector<vector > &A, int B) {
size_t rows = A.size();
size_t cols = A[0].size();
int start = 0, end = (rows*cols)-1;
while (start <= end) {
int mid = start + (end-start)/2;
int row = mid/cols, col = mid%cols;
if (A[row][col] == B)
return 1;
else if (A[row][col] < B)
start = mid + 1;
else
end = mid - 1;
}
return 0;
}


#2

Hi,
You are basically using the entire matrix for searching i.e making use that the entire matrix is basically in a sorted order if you traverse elements row wise. When you do mid/col , it gives u the exact row in which the element is situated (its quite intuitive if u think hard). similarly mid%col will give u the column number in that particular row. After comparison u discard half of matrix and go to other half.
It works because its complexity is log(MN), which is equal to log(M)+log(N), similar to complexity of the editorial solution.