Search a 2D Matrix | LeetCode | Java

Algorithm:

1. Apply Binary Search to find the row (where the potential target might be present)
2. After find the row, apply Binary Search on that row. If the target element is present, we return true otherwise we return false.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        int getRow = findRow(matrix, target);

        if(getRow==-1)
            return false;

        int low = 0;
        int high = matrix[0].length-1;

        while(low<=high){
            int mid = low + (high-low)/2;

            if(matrix[getRow][mid]==target)
                return true;

            else if(matrix[getRow][mid] < target)
                low = mid + 1;

            else
                high = mid - 1;
        }

        return false;
    }

    int findRow(int matrix[][], int target){
        int low = 0;
        int high = matrix.length-1;

        int lastCol = matrix[0].length-1;

        while(low<=high){
            int mid = low + (high-low)/2;

            if(matrix[mid][0]<=target && matrix[mid][lastCol]>=target)
                return mid;

            else if(matrix[mid][0]<target)
                low = mid + 1;

            else
                high = mid-1;
        }

        return -1;
    }
}

Enter fullscreen mode Exit fullscreen mode

Thanks for reading 🙂
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

原文链接：Search a 2D Matrix | LeetCode | Java