DEV Community

Sudeep .U
Sudeep .U

Posted on

Binary Search -Matrix Search

Key points -
1) Search space - 0 to row*cols-1;
Reason - when directly divided by no of columns in a row
You get directly the row and col
Eg : 11 is mid and cols in a row is 4
11/4 -> 2nd row and 3 col in matrix
which is 12th ele -> 3rd row 4th ele
2) Once row and col is derived from mid
Same binary search logic is applied

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int low = 0;
        int high = rows * cols - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int row = mid / cols;
            int col = mid % cols;

            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return false;
    }
}

Enter fullscreen mode Exit fullscreen mode

Top comments (0)