Search a 2D Matrix

1package pkg5leetcode.official75;2 3/*4 * Search a 2D Matrix | LC 745 * APPROACH: Binary search treat matrix as sorted 1D array.6 * COMPLEXITY: Time O(log(mn)), Space O(1)7 */8public class official75_LC74SearchA2DMatrix {9    static boolean searchMatrix(int[][] matrix, int target) {10        int m = matrix.length, n = matrix[0].length;11        int lo = 0, hi = m * n - 1;12        while (lo <= hi) {13            int mid = lo + (hi - lo) / 2;14            int val = matrix[mid / n][mid % n];15            if (val == target) return true;16            if (val < target) lo = mid + 1;17            else hi = mid - 1;18        }19        return false;20    }21 22    public static void main(String[] args) {23        int[][] m = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};24        check(searchMatrix(m, 3), "case1");25        check(!searchMatrix(m, 13), "case2");26        System.out.println("all tests passed");27    }28 29    static void check(boolean cond, String name) {30        if (!cond) throw new AssertionError("FAILED: " + name);31        System.out.println("  PASS " + name);32    }33}