*Java* an easy-to-understand divide and conquer method
The coding seems to be much more complex than those smart methods such as [this one][1], but the idea behind is actually quite straightforward. Unfortunately, i
The coding seems to be much more complex than those smart methods such as [this one][1], but the idea behind is actually quite straightforward. `Unfortunately, it is not as fast as the smart ones.`\n\nFirst, we divide the matrix into four quarters as shown below:\n\n      zone 1      zone 2\n    *  *  *  * | *  *  *  *\n    *  *  *  * | *  *  *  *\n    *  *  *  * | *  *  *  *\n    *  *  *  * | *  *  *  *\n    -----------------------\n    *  *  *  * | *  *  *  *\n    *  *  *  * | *  *  *  *\n    *  *  *  * | *  *  *  *\n    *  *  *  * | *  *  *  *\n      zone 3      zone 4\n\nWe then compare the element in the center of the matrix with the target. There are three possibilities:\n\n\n - center < target. In this case, we discard zone 1 because all elements in zone 1 are less than target.\n\n - center > target. In this case, we discard zone 4.\n\n - center == target. return true.\n\nFor time complexity, if the matrix is a square matrix of size `nxn`, then for the worst case, \n\n    T(nxn) = 3T(n/2 x n/2)\n\nwhich makes \n  \n    T(nxn) = O(n^log3)\n\nCode in Java:\n\n     public boolean searchMatrix(int[][] matrix, int target) {\n        int m = matrix.length;\n        if(m<1) return false;\n        int n = matrix[0].length;\n        \n        return searchMatrix(matrix, new int[]{0,0}, new int[]{m-1, n-1}, target);\n    }\n    \n    private boolean searchMatrix(int[][] matrix, int[] upperLeft, int[] lowerRight, int target) {\n    \tif(upperLeft[0]>lowerRight[0] || upperLeft[1]>lowerRight[1]\n    \t\t\t|| lowerRight[0]>=matrix.length || lowerRight[1]>=matrix[0].length) \n    \t\treturn false;\n    \tif(lowerRight[0]-upperLeft[0]==0 && lowerRight[1]-upperLeft[1]==0)\n    \t\treturn matrix[upperLeft[0]][upperLeft[1]] == target;\n    \tint rowMid = (upperLeft[0] + lowerRight[0]) >> 1;\n    \tint colMid = (upperLeft[1] + lowerRight[1]) >> 1;\n    \tint diff = matrix[rowMid][colMid] - target;\n    \tif(diff > 0) {\n    \t\treturn searchMatrix(matrix, upperLeft, new int[]{rowMid, colMid}, target)\n    \t\t\t\t|| searchMatrix(matrix, new int[]{upperLeft[0],colMid+1}, new int[]{rowMid, lowerRight[1]}, target)\n    \t\t\t\t|| searchMatrix(matrix, new int[]{rowMid+1,upperLeft[1]}, new int[]{lowerRight[0], colMid}, target);\n    \t}\n    \telse if(diff < 0) {\n     \t\treturn searchMatrix(matrix, new int[]{upperLeft[0], colMid+1}, new int[]{rowMid, lowerRight[1]}, target)\n    \t\t\t\t|| searchMatrix(matrix, new int[]{rowMid+1, upperLeft[1]}, new int[]{lowerRight[0], colMid}, target)\n    \t\t\t\t|| searchMatrix(matrix, new int[]{rowMid+1, colMid+1}, lowerRight, target);\n    \t}\n    \telse return true;\n    }\n\n\n  [1]: https://leetcode.com/discuss/48852/my-concise-o-m-n-java-solution
[]