Binary Search - THE EASIEST TO UNDERSTAND APPROACH
We are given that the rows of the matrix are sorted  and so are the columns. We make use of this.\n\ne.g. \n\t\t\t\n\t\t   1  3  5  7\n\t\t   10 11 16 20\n\t\t 
We are given that the rows of the matrix are sorted  and so are the columns. We make use of this.\n\ne.g. \n\t\t\t\n\t\t   1  3  5  7\n\t\t   10 11 16 20\n\t\t   23 30 34 60\n\t\t   \nThis means, we can start searching from the top rightmost element in this matrix, which currently is = 7.\n\nWhy top rightmost only? Because if you see carefully, all elements on the bottom of it are bigger than it. And all elements to the left of it are smaller than it. We can use this property and apply Binary Search.\n\nLets say our target element is  = 11\n\nWe are at element = 7. We see that 11 is > 7 so that means we can discard all the cells that are on left of 7 because we will never find 11 on that side. So we will move to bottom i.e, we go to next row. \n\nNow we are at 20. Here we see that 11 is less than 20. This means we can discard all the cells on the bottom side as the elements on the bottom of 20 are greater than 20 and hence greater than 11. We we move to left side i.e., go to previous column.\n\nNow we are at 16. Again, since 16 > 11, we have to move to left. So we come to previous column.\n\nNow we reach 11. And this is our target value so we return True since we found 11.\n\nSuppose we had to find 40. It is not present in this matrix.  SO first, we start from 7, since 7 < 40, we move to bottom side. Since 20 < 40 we again move to bottom. Since 60 > 40, we move to left. Since 34 < 40, we should move to bottom again. But wait! We are already at the last row and so we cannot move to bottom anymore\n\n\nThis will be one of the conditions for our Binary Search. If the row number exceeds the maximum possible row number in the matrix, then we have to come out of our loop.\n\nNow take another example - Lets say we want to search 4.\n\nThe sequences will be like this - \n\nWe start from 7, since 7 > 4, we move to left of 7. \nWe reach 5. Since 5 > 4, we move to left of 5.\nWe reach 3. Since 3 < 4, we move to bottom side.\nWe reach 11. Since 11 > 4, we move to left side\nWe reach 10. Since 10 > 4, we move to left.\n\nBut wait! Our column became -1 because we were already at 0th column when we were at 10. So that means, if our column index becomes less than 0, then we have to stop.\n\nAnd well, that\'s it. \n\n# **CODE**\n\n```\ndef searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n        n = len(matrix)\n        \n        #We start from the top right corner of the matrix.\n        row = 0\n        col = len(matrix[0])-1\n        \n        # In this way, on the bottom side, all elements are bigger than current element\n        # At left side, all elements are smaller than the current element\n        \n        while(row < n and col >= 0):\n            mid = matrix[row][col]\n            \n            #If the element at this position is the target element we return True\n            if(mid == target): return True\n            \n            # If the element is smaller than this position that means, we need to go to left side of current element\n            if(mid > target): col -= 1\n            #Otherwise we need to move to bottom side\n            else: row += 1\n        \n        return False\n```\n\nThis same approach also works for the "Search a 2D Matrix" problem because while in that problem it is not explicitly mentioned that columns are sorted, they are sorted because each row is sorted and the first element of each row is greater than last element of previous row. Here is the problem - https://leetcode.com/problems/search-a-2d-matrix/\n\n## **GOING ONE STEP FURTHER**\n\nJust like how we can start searching from top rightmost element, we can start searching from bottom leftmost element too. Because in case of bottom left most element, all elements above it are smaller than it and all elements on the right of it are bigger than it.\n\nBut what if we combine both these approaches?\n\n```\ndef searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n        n = len(matrix)\n        m = len(matrix[0])\n\t\t\n        #Top rightmost corner\n        row1 = 0\n        col1 = m-1\n        \n        #Bottom leftmost corner\n        row2 = n - 1\n        col2 = 0\n        \n        #The last condition is to avoid again going to the rows and columns that are already covered\n        while(row1 < n and col1 >= 0 and row2 >= 0 and col2 < m and (col2 <= col1 and row2 >= row1)):\n            mid1 = matrix[row1][col1]\n            mid2 = matrix[row2][col2]\n            \n            # If the element is smaller than mid1 that means we need to move to left side\n            if(mid1 > target): col1 -= 1\n            #Otherwise we need to move to bottom side\n            elif (mid1 < target): row1 += 1\n            \n            # If the element is smaller than mid2 that means we need to move to top side\n            elif(mid2 > target): row2 -= 1\n            #Otherwise we need to move to right side\n            elif(mid2 < target): col2 += 1\n            \n            else: return True\n                \n        \n        return False\n```\n
['Binary Search', 'Binary Tree', 'Python']