DEV Community

truongductri01
truongductri01

Posted on

74. Search a 2D Matrix

Problem: 74. Search a 2D Matrix

Approach

/**
Definitely binary search

2 steps:
- search for which row the target should fall into 
- then search within that row for the target 


How to search for which row 
hasRow = false;
int rowIdx = -1;
leftRow and rightRow

while (leftRow <= rightRow) {
    int midRow;

    if (target within midRow) {
        hasRow = true;
        rowIdx = midRow;
    }

    if (target < midRow[0]) {
        right = midRow - 1;
    } else if (target > midRow[size - 1]) {
        left = midRow + 1;
    }
}

if not found row: return false;

else, find within the row

*/
Enter fullscreen mode Exit fullscreen mode

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        boolean hasRow = false;
        int rowIdx = -1;

        int leftRow = 0;
        int rightRow = matrix.length - 1;
        int columns = matrix[0].length;

        while (leftRow <= rightRow) {
            int midRow = (leftRow + rightRow) / 2;

            if (target >= matrix[midRow][0] && target <= matrix[midRow][columns - 1]) {
                hasRow = true;
                rowIdx = midRow;
                break;
            } else if (target < matrix[midRow][0]) {
                rightRow = midRow - 1;
            } else if (target > matrix[midRow][columns - 1]) {
                leftRow = midRow + 1;
            }
        }

        if (!hasRow) {
            return false;
        }

        int left = 0;
        int right = columns - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (target == matrix[rowIdx][mid]) {
                return true;
            } else if (target < matrix[rowIdx][mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return false;
    }
}
Enter fullscreen mode Exit fullscreen mode

Image of Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay