So given a matrix m x n, you need to find the target value. The integers in each row are sorted from left to right, and the first integer of each row is greater than the last integer of previous row.

For example, given a target = 3 and a matrix as below

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

will output result true because 3 can be found in the matrix.

Now, for starter, we can brute force the way out to find out the result.

    public boolean searchMatrix(int[][] matrix, int target) {
        
        if(matrix == null || matrix.length == 0){
            return false;
        }
        if(matrix[0] == null || matrix[0].length == 0){
            return false;
        }
        
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) { 
                if(matrix[row][col] == target){
                    return true;
                }      
            } 
        }
        
        return false; 
    }

Of course, this is not the optimal solution. We need to optimize it using binary search method. Can we apply the binary search template into this problem? Sure, we can! Here's how:

First, we can use binary serach to find where the row the target should be located at. Once we have located the row, then we can perform binary search again to find out the column.

    public boolean searchMatrix(int[][] matrix, int target) {
        
        if(matrix == null || matrix.length == 0){
            return false;
        }
        
        if(matrix[0] == null || matrix[0].length == 0){
            return false;
        }
        
        int row = matrix.length;
        int column = matrix[0].length;  
        
        // find the row index, the last number <= target 
        int start = 0, end = row - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (matrix[end][0] <= target) {
            row = end;
        } else if (matrix[start][0] <= target) {
            row = start;
        } else {
            return false;
        }
        
        // find the column index, the number equal to target
        start = 0;
        end = column - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (matrix[row][start] == target) {
            return true;
        } else if (matrix[row][end] == target) {
            return true;
        }
        
        return false;
    }

There we have it!

Post was published on , last updated on .

Like the content? Support the author by paypal.me!