Solving Leetcode 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

Basically what its asking is given a 2D matrix of integers, find whether the target is present in the matrix or not. You can solve this problem using either a binary search or a linear search. 1. Binary search: First, find the row where the target is likely to be located using binary search. Then, do a linear search in that row to find the target.

2. Linear search: Simply scan through the matrix until you find the target.

The binary search approach is more optimal, as it has a time complexity of O(log(m) + log(n)), while the linear search approach has a time complexity of O(m * n). This work because the matrix is sorted.

First, we need find the row where the target is likely to be located using binary search. Then, do a linear search in that row to find the target.

We can start by finding the midpoint of the matrix. If the target is less than the element at the midpoint, search the left half of the matrix. If the target is greater than the element at the midpoint, search the right half of the matrix. Repeat this process until you find the row where the target is likely to be located. How do you do the second part? Once you have found the row where the target is likely to be located, you can do a linear search in that row to find the target. Start at the beginning of the row and scan through until you find the target or reach the end of the row.

Code in JavaScript:

var searchMatrix = function(matrix, target) {
          let row = 0;
        let col = matrix[0].length - 1;
        
        while(row < matrix.length && col >= 0) {
            if(matrix[row][col] === target) {
                return true;
            } else if(matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
};

Code in Java:

public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        int i = 0;
        int j = col-1;
        while(i<row && j>=0){
            if(matrix[i][j] == target){
                return true;
            }
            else if(matrix[i][j] > target){
                j--;
            }
            else{
                i++;
            }
        }
        return false;
    }