Binary search of a Matrix

Question

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

-Integers in each row are sorted from left to right.
-The first integer of each row is greater than or equal to the last integer of the previous row.

Example:

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return 1 ( 1 corresponds to true )

Return 0 / 1 ( 0 if the element is not present, 1 if the element is present ) for this problem

My solution works on NetBeans but fails on the website. Any help will be appreciated. https://www.interviewbit.com/problems/matrix-search/

public class Solution {

    public int searchMatrix(ArrayList<ArrayList<Integer>> a, int b) {
        int r = a.size();
        int c = a.get(0).size();

        int start = 0;
        int end = r - 1;
        // default value is last row for edge case
        int biRow = r -1; // row to search column

        //binary search 1st value of rows
        while (start <= end) {
            int mid = (start + end) / 2;
            if (b == a.get(mid).get(0)) {
                return 1;
            }

            if (a.get(mid).get(0) < b && b < a.get(end).get(0)) {
                if (mid + 1 >= end) {
                    biRow = mid;
                    break;
                }
            } if (b < a.get(mid).get(0)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        //binary search column of biRow
        start = 0;
        end = c-1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (b == a.get(biRow).get(mid)) {
                return 1;
            }
            if (b < a.get(biRow).get(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return 0;
    }
}

Answer 1

Okay, the first thing you MUST NOT do is that, you cannot physically concat the matrix into a 1D vector, as this is O(N*M) which is linear and not what we want.

// Easy but TLE code
int Solution::searchMatrix(vector<vector<int> > &A, int B) {
    vector<int> v;
    for(auto a : A) v.insert(v.end(), a.begin(), a.end());
    return binary_search(v.begin(), v.end(), B);
}

So the point is, you have to do binary search directly on the matrix, and that is pretty much the same (except you have to write binary search your own now).

As you did not really access all of the elements, this is O(lg (N*M))

// Less Easy but AC code
int Solution::searchMatrix(vector<vector<int> > &A, int B) {
    int m = A.size(), n = A[0].size(), lo = 0, hi = m*n-1, mi, row, col;
    while(lo <= hi){
        mi = lo + ((hi-lo) >> 1);
        row = mi / n;
        col = mi % n;
        if(A[row][col] == B) return 1;
        else if(A[row][col] > B) hi = mi - 1;
        else lo = mi + 1;
    }
    return 0;
}