Search a 2D Matrix

Search a 2D Matrix

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 the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true

class Solution {
    pair<bool, int> process(vector<vector<int> >& matrix, int const start,
      int const end, int const target, bool rowSearch = false, int row = 0){
        int const halfIndex = start + (end-start+1)/2;
        int first_val, last_val, mid_val;
        if(rowSearch){
            first_val = matrix[row][start];
            last_val = matrix[row][end];
            mid_val = matrix[row][halfIndex];
        }else{        
            first_val = matrix[start][0];
            last_val = matrix[end][0];
            mid_val = matrix[halfIndex][0];
        }
        if (start == end){
            if (target != mid_val) return pair<bool, int>(false, start);
            else return pair<bool,int>(true, start);
        }
        return ( target < mid_val? 
            process(matrix, start, halfIndex-1, target, rowSearch, row):
            process(matrix, halfIndex, end, target, rowSearch, row)  );
            
        
    }
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(matrix.empty() || matrix[0].empty() || target < matrix[0][0] || target > matrix.back().back()) return false;
        pair<bool, int> colResult = process(matrix, 0, matrix.size()-1, target);
        if (colResult.first) return true;
        return process(matrix, 0, matrix[0].size()-1, target, true, colResult.second).first;
    }
};