2.2 Search a 2D Matrix

Write and efficient search for M x N matrix

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

Logical steps

1. Binary search for row, in all matrix[i][0], get startRow and endRow. Be careful when checking exact rows, check common mistakes
2. Binary search for col, in all matrix[row][i], get startCol and endCol
3. Compare target with matrix[row][startCol] and matrix[row][endCol] and get final answer

Code Template

// search for startRow and EndRow
int startRow = 0;
int endRow = numOfRow - 1;

while (startRow + 1 < endRow) {
    int midRow = (startRow+endRow)/2;

    if (target==matrix[midRow][0]){
        return true;
    }else if(target > matrix[midRow][0]) {
        startRow = midRow;
    }else{
        endRow = midRow;
    }
}

int row = 0;

/** Figure out the actual row
* return false when target is too big or small
* for matrix
*/
if (target < matrix[startRow][0]
    || target > matrix[endRow][numOfCol-1]) {
    return false;
}else if (target < matrix[endRow][0]){
    row = startRow;
// make sure to use else if here, since target in first row
// is less than end of end row as well
}else if (target <= matrix[endRow][numOfCol-1]){
    row = endRow;
}

// search for startCol and endCol
int startCol = 0;
int endCol = numOfCol - 1;

while(startCol + 1 < endCol) {
    int midCol = (startCol+endCol)/2;

    if (target == matrix[row][midCol]){
        return true;
    }else if(target > matrix[row][midCol]){
        startCol = midCol;
    }else{
        endCol = midCol;
    }
}


// figure out the exact col
if (target == matrix[row][startCol])
    return true;

if (target == matrix[row][endCol])
    return true;

return false;

Common mistakes

1. When finding exact rows, forget to use else if statements, endRow rewrites startRow

    if (target < matrix[endRow][0]){
        row = startRow;
    } 
    /** this is a mistake example
    * if target is in startRow, target is also < matrix[endRow][numOfCol-1]
    * row = endRow will rewrite row variable
    */
    if (target <= matrix[endRow][numOfCol-1]){
        row = endRow;
    }
   

2. When finding exact rows, forget to consider very end element of end row (target == matrix[endRow][numOfCol-1])

    if (target < matrix[startRow][0]
        || target > matrix[endRow][numOfCol-1]) {
        return false;
    }else if (target < matrix[endRow][0]){
        row = startRow;
    /**this is a mistake example
    * if target = last element in matrix
    * it will not be found in end row
    * since target == matrix[endRow][numOfCol-1]
    * is not considered
    */
    }else if (target < matrix[endRow][numOfCol-1]){
        row = endRow;
    }