C++ linear binary search w/ subroutine for clarity


  • 0
    D

    The restrictions on the matrix clearly show the intention for us to search in a linear space.

    They always say interviewers like to see you break out subroutines where it makes sense and helps keeps things clear. I used a subroutine to do the lookup by translating the linear index into (row,col). Main routine then does does simple binary search. 12ms runtime.

    class Solution {
    public:
        int getValue( vector<vector<int>>& matrix, int idx ) {
            int rowSize = matrix[0].size();
            int r = idx / rowSize;
            int c = idx % rowSize;
            return matrix[r][c];
        }
        
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (matrix.empty()) return false;
            if (matrix[0].empty()) return false;
            int lo = 0;
            int hi = matrix[0].size() * matrix.size() - 1;
            while( lo < hi ) {
                int mid = (lo+hi)/2;
                int val = getValue(matrix,mid);
                if (val < target) lo = mid+1;
                else if (val > target) hi = mid;
                else return true;
            }
            return ( getValue(matrix,lo) == target );
        }
    };
    

Log in to reply
 

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