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;

}

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

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.