Search a 2D Matrix

LeetCode Q 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.

Solution

We can solve this problem by two methods.

Method 1:

• Use binary search to find the row no.
• Use binary search to find the number in that row.

Method 2:

• Take the matrix as an array, and then do the binary search

key point is how to translate the index to row and col no.
nums[index] = nums[index / col][index % col];

Code: Method 1

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0 
        || target < matrix[0][0])
        return false;
    
    int row = matrix.length, col = matrix[0].length;
    // do binary search once
    int left = 0, right = row * col - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int number = matrix[mid / col][mid % col];
        if (number == target)
            return true;
        else if (number > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return false;
}

Code: Method 2

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0 
        || target < matrix[0][0])
        return false;
    
    int row = matrix.length, col = matrix[0].length;
    
    // 1. find in which row the target may exist, use start as the row index
    int start = 0, end = row - 1, rowIndex = -1;
    while (start < end) {
        int mid = (start + end) / 2;
        if (matrix[mid][0] == target)
            return true;
        if (matrix[mid][0] > target)
            end = mid - 1;
        else {
            if (mid == row - 1 || matrix[mid + 1][0] > target) {
                start = mid; break;
            }
            start = mid + 1;
        }    
    }
    // now the start represents that row index
    // then use binary searth to find the element
    return helper(matrix[start], 0, col - 1, target);
}

private boolean helper(int[] nums, int left, int right, int target) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target)
            return true;
        else if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return false;
}