LeetCode: Search a 2D Matrix

For example,

Consider the following matrix:

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

Given target = 3, return true.

---

Use binary search to find the row first and then find the element.

C++ Code:

/*
 * func: search_matrix_helper
 * goal: recursive helper function to do matrix binary search
 * @param matrix: input matrix
 * @param row_start: starting row searching index
 * @param row_end: ending row searching index
 * @param column_start: starting column searching index
 * @param column_end: ending column searching index
 * @param target: target value
 * return: true or false
 */
bool search_matrix_helper(const vector<vector<int> > &matrix, int row_start, int row_end, int column_start, int column_end, int target){
    if(row_start >= row_end){
        if(column_start >= column_end){
            return matrix[row_start][column_start] == target;
        }
        
        int mid = column_start + (column_end - column_end)/2;
        if(matrix[row_start][mid] == target){
            return true;
        }else if(matrix[row_start][mid] < target){
            return search_matrix_helper(matrix, row_start, row_end, mid+1, column_end, target);
        }else{
            return search_matrix_helper(matrix, row_start, row_end, column_start, mid-1, target);
        }
    }
    
    int mid = row_start + (row_end - row_start)/2;
    if(matrix[mid][0] == target){
        return true;
    }else if(matrix[mid][0] > target){
        return search_matrix_helper(matrix, row_start, mid-1, column_start, column_end, target);
    }else if(matrix[mid][0] < target && target <= matrix[mid][column_end]){
        return search_matrix_helper(matrix, mid, mid, column_start, column_end, target);
    }else{
        return search_matrix_helper(matrix, mid + 1, row_end, column_start, column_end, target);
    }
}

/*
 * func: search_matrix
 * goal: find the target in the sorted matrix
 * @param matrix: input matrix
 * @param target: input target
 * return: true or false
 */
/*
 * Use the idea of binary search
 * complexity: time O(log(mn)), space O(1)
 */
bool search_matrix(const vector<vector<int> > &matrix, int target){
    int m = matrix.size();
    if(m == 0){
        return false;
    }
    int n = matrix[0].size();
    return search_matrix_helper(matrix, 0, m-1, 0, n-1, target);
}

Python Code:

# func: search value in a sorted matrix
# @param matrix: input matrix
# @param target: target value
# @return: True or False
# complexity: time O(log(mn)), space O(1)
def search_matrix(matrix, target):
    m = len(matrix)
    if m == 0:
        return False
    n = len(matrix[0])

    start_row = 0
    end_row = m-1
    while start_row < end_row:
        mid = start_row + (end_row - start_row)/2
        if matrix[mid][0] == target:
            return True
        elif matrix[mid][0] > target:
            end_row = mid-1
        elif matrix[mid][0] < target <= matrix[mid][-1]:
            start_row = mid
            break
        else:
            start_row = mid + 1

    start_col = 0
    end_col = n-1
    while start_col <= end_col:
        mid = start_col + (end_col - start_col)/2
        if matrix[start_row][mid] == target:
            return True
        elif matrix[start_row][mid] > target:
            end_col = mid-1
        else:
            start_col = mid + 1
    return False