LeetCode - Search a 2D Matrix | Darren's Blog

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

Keyword: Binary Search

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

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)

            return false;

        int m = matrix.length, n = matrix[0].length;

        // In a row-major manner, the matrix is in essence a sorted array

        // Binary search for target

        int left = 0, right = m*n-1;

        while (left <= right) {

            int center = (left+right) / 2;

            int i = center / n, j = center % n; // Index in the matrix for the center value

            if (matrix[i][j] == target)     // Target found

                return true;

            if (matrix[i][j] < target)      // Target at the right half

                left = center + 1;

            else        // Target at the left half

                right = center - 1;

        }

        return false;   // Target not found

    }

Read full article from LeetCode - Search a 2D Matrix | Darren's Blog