A different O(m+n) solution! 2D binary search, no trickery involved, methodical
Intuition\nAFAIK, people posted 2 types of solution:\n- mostly people are reposting the same clever trick in O(m+n) (starting from top-right or bottom-left corn
# Intuition\nAFAIK, people posted 2 types of solution:\n- mostly people are reposting the same clever trick in O(m+n) (starting from top-right or bottom-left corner and moving accordingly)\n- a suboptimal divide and conquer approach\n\nBoth methods leave me unsatisfied: you could easily miss the trick in an interview if your mind just doesn\'t wander the right way. It feels too random to rely on a trick, and I prefer to have at least one more methodical approach available.\nThe divide and conquer is the most methodical and you could more easily come up with it, eespecially by analogy with other problems you have solved before. However it is suboptimal\n\nHere, we explore an O(m+n) divide and conquer approach that you can methodically come up with if you know the binary search\nIt is essentially a **2D binary search**\nN.B: feel free to correct me if I got the complexity wrong, I am not 100% certain. \n\n\n\n# Approach\nThe idea is the following:\nTake your current matrix and select the middle row. In the middle row, look for the target with a binary search. If you find it, you\'re done. If not, take note of the position of the last element smaller than the target and the first larger (represented by the < and > below)\n```\n|                                   |\n|                                   |\n|                                   |\n|----------<>-----------------------| (binary search on middle row)\n|                                   |\n|                                   |\n|                                   |\n```\nThis element, that we will call the pivot point yields precious information, because we know that we can discard all the elements in the top-left quadrant will be smaller, and all the elements in the bottom right quadrant will be larger than target by definition of the ordering of the matrix:\n```\n|          |                        |\n|ELIMINATED|                        |\n|          |                        |\n|----------<>-----------------------|\n|           |                       |\n|           |      ELIMINATED!      |\n|           |                       |\n```\nWe can the explore the 2 remaining matrices recursively.  This goes on until you\'ve divided the submatrices into single rows, after which you can move on to the next submatrix in the recursive stack call. Here is what the search space might look like after the next iteration.\n```\n|          |    ELIM       |        |\n|ELIMINATED|---------------<>-------|\n|          |                | ELIM  |\n|----------<>-----------------------|\n|           |                       |\n|           |      ELIMINATED!      |\n|           |                       |\n```\nAs we see, the philosophy of this algorithm just builds on from the simple binary search. It basically uses a bin search in both dimensions of the matrix to divide it into submatrices and eliminating half of them each time, until only a single row remains\n\n# Complexity\n- Time complexity:\n**O(m+n)**\n\nOkay here is the tricky part. Calculating the complexity of this recursion is a bit complicated and if you think I did it wrong, please let me know.\n\nThis is a recursive algorithm. Let\'s call $N=m*n$ the total number of elements in a submatrix. At each step of the recursion, we cut the size of the submatrix in half. More accurately, we divide it into four quadrants, and we only explore two of the quadrants, one with K elements and the other with L elements so that $K+L=N/2$. This subdivision is done in O(log(n)) thanks to a binary search\nSo the master equation for this recursion could be written as:\n\n$$T(N)=T(K)+T(L)+O(log(n))$$, where $$K+L=N/2$$\n\n[The Akra-Bazzi theorem](https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method) tells us that we need to find the integer $p$ so that: \n$$K^p+L^p=N^p$$\nBad news, we can\'t. It depends on how exactly the submatrix is split between K and L. **But we can get an upper bound for p**. Because the square root function is concave, we can write:\n$$\\frac{\\sqrt K + \\sqrt L}{2}<\\sqrt{\\frac {K + L}{2}}$$\n$$\\frac{\\sqrt K + \\sqrt L}{2}<\\sqrt{\\frac {N}{4}}$$\n$$\\sqrt K + \\sqrt L< \\sqrt N$$\n**therefore, 1/2 is an upper bound for p** (only smaller values of p could satisfy the equality)\n\nTherefore, the Akra Bazzi theorem tells us that our complexity will be bounded by:\n$$T(N)< \\Theta \\left(\\sqrt N\\left(1+\\int _{1}^{N}{\\frac  {g(u)}{u^{{3/2}}}}du\\right)\\right)$$\nWe can show with an integration by part that the integral is actually just O(1), so **our complexity is bounded by $O(\\sqrt N)$**\n\nWe note that, according to the [inequality of arithmetic and geometric means](https://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means),\n$$\\sqrt N=\\sqrt{m*n}<=\\frac{m+n}{2}$$\nSo $$T(N)<O(m+n)$$\n\n**Our complexity is at worst O(m+n). It is on-par with the "trick" solution in terms of time complexity**\n\n- Space complexity:\nO(1) \n\n# Code\n\nThe code is probably ugly and could be written better but I tried to make it clear with comments. This is not the main point anyway, I mostly wanted to share the different approach, not so much the details of the implementation\n\n```\nclass Solution:\n    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n       \n        # helper function for binary search\n        # inputs:   -row of the matrix that we are exploring\n        #           -starting index of the row (based on the current submatrix)\n        #           -final index of the row\n        # returns True if target is found, otherwise, returns the largest value that is < target\n        def bsearch(row,cstart,cend):\n            left=cstart\n            right=cend\n            while left<=right:\n                mid=(left+right)//2\n                if matrix[row][mid]==target:\n                    return True\n                elif matrix[row][mid]<target:\n                    if mid+1>cend or matrix[row][mid+1]>target: return mid\n                    left=mid+1\n                else:\n                    if mid-1<cstart or matrix[row][mid-1]<target: return mid-1\n                    right=mid-1\n\n\n        # main function that does the matrix splitting based on the pivot point\n        # input:    -rstart,rend : starting row and final row of current submatrix\n        #           -cstart,cend : starting column and final column\n        def dichotomy2D(rstart,rend,cstart,cend):\n            # checking if we have reached some kind of stupid index that indicates end of search\n            if cstart>cend or rstart<0 or rend >= len(matrix) or rstart>rend:\n                return False\n            #we select the middle row of the current submatrix\n            row=(rstart+rend)//2\n            #we perform the binary search on the middle row and retrun True if target is found\n            split=bsearch(row,cstart,cend)\n            if split is True:\n                return True\n            #otherwise, we subdivise the array into bottom left (from [row+1,cstart] to [rend,split]) and top right(from[row-1,split+1] to [rstart,cend]), and we check those recursively\n            return dichotomy2D(max(row+1,rstart),rend,cstart,split) or dichotomy2D(rstart,min(row-1,rend),res+1,cend)\n\n        return dichotomy2D(0,len(matrix)-1,0,len(matrix[0])-1)\n```
['Binary Search', 'Divide and Conquer', 'Matrix', 'Python3']