C++ | Binary Search (2 variations) | O(m+n) | Explanation (with example) + Diagram
EXPLANATION\nConsider the below diagram.\n\n\n\nTarget : Green (13), Starting point : Yellow (15).\n Traversal Path : Orange (15 -> 11, 12, 16, 9, 14 ->13).\n\n
**EXPLANATION**\nConsider the below diagram.\n\n![image](https://assets.leetcode.com/users/images/9d344366-1ff3-4fbe-930d-3aaff907f204_1614093877.1058805.png)\n\n**Target** : Green (13), **Starting point** : Yellow (15).\n **Traversal Path** : Orange (15 -> 11, 12, 16, 9, 14 ->13).\n\n- Start iterating the `matrix` from **top right corner** of the `matrix`, that is `matrix[0][size of column -1]`.\n- If `matrix[i][j]==target`, return **true**.\n- If the `target` is less than `matrix[i][j]`, then move **leftwards** (*decrease the column*), that is `--j`.\n- If the `target` is greater than `matrix[i][j]`, then move **downwards** (*increase the row*), that is `++i`.\n\n- If the `target` element is *not found* then after *exiting* the above loop, return **false**.\n\n**CODE IMPLEMENTATION (Variation 1)**\n```\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int n=matrix.size();\n        int m=matrix[0].size();\n        \n        // start from the [first row, last column] element\n        int i=0;\n        int j=m-1;\n        while(i<n && j>=0){\n            if(matrix[i][j]==target) // target found\n                return true;\n            else if(matrix[i][j]>target) //target is smaller, go leftwards\n                --j; // decrease the column index\n            else // target is larger, go downwards\n                ++i; // increase the row index\n        }\n        return false; // target not found\n    }\n};\n```\n\nConsidering, *m* = length of column and *n* =  length of row.\n\n**TIME COMPLEXITY: O(m+n)**\nFor any case, the path traversed will be the shortest path from the top right corner to the target element. Say target element is at `[ti, tj]` and top right corner (*starting index*) is `[0,m - 1]`, so the total path traversed will be `[ti - 0, (m - 1) - tj]`, so the time taken is `O(ti + m - 1 - tj)`. Now, according to the constraints given in question, the worst case will be when `ti = n-1` and `tj = 0`, that is target element is at `matrix[n-1, 0]`. So, the worst-case time complexity will be `O(n - 1 + m  - 1 - 0)`, that is `O(n + m)` (asymptotically).\n\n**SPACE COMPLEXITY: O(1)**\nNo extra space is used.\n\n\n**CODE IMPLEMENTATION (Variation 2)**\nAs suggested by [@Niks291](https://leetcode.com/Niks291), we can also start from the **bottom left corner** of the `matrix`, that is from `matrix[size of row - 1][0]` along with changing some conditions within the loop.\n```\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int n=matrix.size();\n        int m=matrix[0].size();\n        \n        // start from the [last row, first column] element\n        int i=n-1;\n        int j=0;\n        while(j<m && i>=0){\n            if(matrix[i][j]==target) // target found\n                return true;\n            else if(matrix[i][j]>target) //target is smaller go upwards\n                --i; // decrease the row index\n            else // target is larger go rightwards\n                ++j; // increase the column index\n        }\n        return false; // target not found\n    }\n};\n```
['C', 'Binary Tree']