74. 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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
Output: false

Example 3:

Input: matrix = [], target = 0
Output: false

Constraints:

• m == matrix.length

• n == matrix[i].length

• 0 <= m, n <= 100

• -104 <= matrix[i][j], target <= 104

typedef pair<int,int> pii;
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(!m) return false;
        int n = matrix[0].size();
        if(!n) return false;
        int lo = getIndex(n, 0, 0);
        int hi = getIndex(n, m-1, n-1);
        while(lo <= hi){
            int mid = (lo + hi)/2;
            pii node = getPair(n, mid);
            if(matrix[node.first][node.second] < target){
                lo = mid + 1;
            }else if(matrix[node.first][node.second] > target){
                hi = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
    pii getPair(int n, int index){
        return pii(index/n, index%n);
    }
    int getIndex(int n, int i, int j){
        return (i*n + j);
    }
};