0074 - Search a 2D Matrix

0074 - Search a 2D Matrix

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.

Examples

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false

Constraints

m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -104 <= matrix[i][j], target <= 104

Java Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int columns = matrix[0].length;
        if(rows == 0) return false;
        
        int left = 0;
        int right = rows*columns - 1;
        while(left <= right) {
            int pivot = (left + right) / 2;
            int pivotValue = matrix[pivot/columns][pivot%columns];
            if(target == pivotValue) return true;
            else {
                if(target < pivotValue) right = pivot - 1;
                else left = pivot + 1;
            }
        }
        return false;
    }
}