Java Binary Search Solution with Illustration and Explanation
\n\nGiven a (sub)matrix enclosed by (lox, loy) and (hix, hiy), just recursively search any 3 of 4 quadrants (excluding the impossible one) after comparing the t
![image](https://assets.leetcode.com/users/images/b889c8d3-22ec-4074-b9ef-70059424c92d_1621867186.9592545.png)\n\nGiven a (sub)matrix enclosed by `(lox, loy)` and `(hix, hiy)`, just recursively search any 3 of 4 quadrants (excluding the impossible one) after comparing the `target` value with the value of the middle point `(i, j)`.\n\n```\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        return search(matrix, target, 0, 0, m-1, n-1);\n    }\n    \n    private boolean search (\n        int[][] mat,\n        int t,\n        int lox,\n        int loy,\n        int hix,\n        int hiy\n    ) {\n        if (lox > hix || loy > hiy) return false;\n        int i = lox + (hix - lox) / 2;\n        int j = loy + (hiy - loy) / 2;\n        if (mat[i][j] < t) {\n            return search(mat, t, lox, j+1, i, hiy)    // q1\n                || search(mat, t, i+1, loy, hix, j)    // q3\n                || search(mat, t, i+1, j+1, hix, hiy); // q4\n        } else if (mat[i][j] > t) {\n            return search(mat, t, lox, j, i-1, hiy)    // q1\n                || search(mat, t, i, loy, hix, j-1)    // q3\n                || search(mat, t, lox, loy, i-1, j-1); // q2\n        } else {\n            return true;\n        }\n    }\n}\n```
['Binary Tree', 'Java']