SearchA2DMatrix.java

/**
 * You are given an m x n integer matrix matrix with the following two properties:
 *
 * Each row is sorted in non-decreasing order.
 * The first integer of each row is greater than the last integer of the previous row.
 * Given an integer target, return true if target is in matrix or false otherwise.
 *
 * You must write a solution in O(log(m * n)) time complexity.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * Output: true
 * Example 2:
 *
 *
 * 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
 */

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int st = 0, en = (m - 1);

        while(st <= en){
            int mid = (st + en) / 2;
            if(matrix[mid][0] > target) en = mid - 1;
            else st = mid + 1;
        }
        int ind = en;
        if(ind < 0 || ind >= m) return false;
        st = 0; en = n - 1;
        while(st < en){
            int mid = (st + en) / 2;
            if(matrix[ind][mid] > target) en = mid - 1;
            else if(matrix[ind][mid] < target) st = mid + 1;
            else return true;
        }


        return false;
    }
}