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.

Search a 2D Matrix.cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        
        //search row first
        int low = 0;
        int high = matrix.size();
        
        while(low < high) {
            int mid = low + (high - low) / 2;
            int cur = matrix[mid][0];
            
            if(cur == target) {
                return true;
            } else if(cur > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        --low;
        
        if(low < 0) {
            return false;
        }
        
        return bin(matrix[low], target);
        
    }
    
    bool bin(vector<int>& arr, int target) {
        int low = 0;
        int high = arr.size();
        while(low < high) {
            int mid = low + (high - low) / 2;
            int cur = arr[mid];
            
            if(cur == target) {
                return true;
            } else if(cur > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        return false;
        
    }
};