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:

    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;
    }

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

---

There we have it!

Post was published on 3 Jan 2020, last updated on 22 Dec 2020.

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