JS, Python, Java, C++ | Binary Search Solution w/ Visual Explanation
(Note: This is part of a series of Leetcode solution explanations (index). If you like this solution or find it useful, please upvote this post.)\n\n---\n\n####
*(Note: This is part of a series of Leetcode solution explanations ([**index**](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThe naive approach here would be to check every cell at a **time complexity** of **O(m * n)**. The obvious improvement on this would be to use a **binary search** on each row to shorten this to **O(m * log n)**. But since the matrix (**M**) is sorted both by row and by column, we can actually think of each **cell** (**M[i][j]**) as being a midpoint in a longer "row", including all the cells to the left as well as below the current cell.\n\nIf we start from the top right corner of **M** and treat this like a modified binary search, we can eliminate an entire row or an entire column each time we check a **cell**:\n\n![Visual 1](https://i.imgur.com/HG6ZPns.png)\n\nWe\'ll then just need to adjust our **i** or **j** value to move to the top right corner "midpoint" of the remaining matrix each time to narrow in on our target (**T**):\n\n![Visual 2](https://i.imgur.com/b1gvHg0.png)\n\nThis will drop the time complexity to **O(m + n)**.\n\n(*Note: This works just as well when starting from the bottom left corner.*)\n\n---\n\n#### ***Implementation:***\n\nFor all except Java we can use the **bitwise NOT** operator (**~**) to check for boundary condition of **j** because it will return a falsy value (**0**) only when **j** is **-1**.\n\n(*Note: Some people are achieving "faster" results by exploiting a design flaw in the testing suite. It appears that the test includes one or more loops of the same matrix input and people have had the idea to clear the matrix before returning the answer, which will make the rest of said loop easier to process, as the mutated matrix will be used in subsequent iterations of the test.*)\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **280ms / 41.8MB** (beats 98% / 78%).\n```javascript\nvar searchMatrix = function(M, T) {\n    let y = M.length, i = 0, j = M[0].length - 1\n    while (i < y && ~j) {\n        let cell = M[i][j]\n        if (cell === T) return true\n        else if (cell > T) j--\n        else i++\n    }\n    return false\n};\n\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **148ms / 20.4MB** (beats 99% / 98%).\n```python\nclass Solution:\n    def searchMatrix(self, M: List[List[int]], T: int) -> bool:\n        y, i, j = len(M), 0, len(M[0]) - 1\n        while i < y and ~j:\n            cell = M[i][j]\n            if cell == T: return True\n            elif cell > T: j -= 1\n            else: i += 1\n        return False\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **4ms / 44.2MB** (beats 100% / 96%).\n```java\nclass Solution {\n    public boolean searchMatrix(int[][] M, int T) {\n        int y = M.length, i = 0, j = M[0].length - 1;\n        while (i < y && j >= 0) {\n            int cell = M[i][j];\n            if (cell == T) return true;\n            else if (cell > T) j--;\n            else i++;\n        }\n        return false;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **60ms / 14.6MB** (beats 96% / 92%).\n```c++\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& M, int T) {\n        int y = M.size(), i = 0, j = M[0].size() - 1;\n        while (i < y && ~j) {\n            int cell = M[i][j];\n            if (cell == T) return true;\n            else if (cell > T) j--;\n            else i++;\n        }\n        return false;\n    }\n};\n```
['C', 'Python', 'Java', 'JavaScript']