class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int> > &matrix, int target) {
        // write your code here
        int m=matrix.size();
        int n=matrix[0].size();
        return searchRec(matrix, 0, n-1, 0, m-1, target);
    }

    int searchRec(vector<vector<int>> &matrix, int l, int r, int u, int d, int target) {
        if(l>r || u>d) return 0;
        int um=u+(d-u)/2;
        int lm=binary(matrix[um], l, r, target);
        int ur=searchRec(matrix, lm, r, u, um-1, target);
        int ld=searchRec(matrix, l, lm-1, um, u, target);
        return (matrix[um][lm]==target? 1:0) + ur + ld;
    }

    int binary(vector<int> &row, int l, int r, int target) {
        if(row[r]<target) return r+1;
        int low=l, high=r;
        int mid=(high+low+1)/2;
        while(low<high) {
            if(mid>=target) {
                high=mid;
            } else {
                low=mid+1;
            }
            mid=(high+low+1)/2;
        }
        return mid;
    }
};