O(log(m)+log(n)) Double Directional Binary Search in Java
Idea:\n- Search from top-right corner of the matrix;\n- If the current number is smaller than target, binary search row from row + 1 to rows - 1 given the curre
**Idea:**\n- Search from top-right corner of the matrix;\n- If the current number is smaller than `target`, binary search row from `row + 1` to `rows - 1` given the current `col`;\n- Else if the current number is greater than `target`, binary search col from `0` to `cols - 1` given the current `row`.\n\n**Code:**\n```java\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        int rows, cols;\n        // Input check\n        if (matrix == null || (rows = matrix.length) == 0 || (cols = matrix[0].length) == 0) {\n            return false;\n        }\n        \n        for (int row = 0, col = cols - 1; row >= 0 && row < rows && col >= 0 && col < cols;) {\n            if (matrix[row][col] == target) {\n                // Found target\n                return true;\n            }\n            if (matrix[row][col] < target) {\n                // Target is greater than current number, binary search row in [row + 1, rows - 1] in current column\n                row = binarySearchInCol(matrix, target, rows, cols, col, row + 1, rows - 1);\n            } else {\n                // Target is smaller than current number, binary search col in [0, col - 1] in current row\n                col = binarySearchInRow(matrix, target, rows, cols, row, 0, col - 1);\n            }\n        }\n        return false;\n    }\n    \n    private int binarySearchInRow(int[][] matrix, int target, int rows, int cols, int row, int low, int high) {\n        if (low > high) {\n            return cols;\n        }\n        while (low < high) {\n            int mid = low + ((high - low) >> 1);\n            if (matrix[row][mid] >= target) {\n                high = mid;\n            } else {\n                low = mid + 1;\n            }\n        }\n        return low;\n    }\n    \n    private int binarySearchInCol(int[][] matrix, int target, int rows, int cols, int col, int low, int high) {\n        if (low > high) {\n            return rows;\n        }\n        while (low < high) {\n            int mid = low + ((high - low) >> 1);\n            if (matrix[mid][col] >= target) {\n                high = mid;\n            } else {\n                low = mid + 1;\n            }\n        }\n        return low;\n    }\n}\n```
[]