240. Search a 2D Matrix I
Intuition\n Describe your first thoughts on how to solve this problem. \nSolve it by using binary search on each row\n\n# Approach\n Describe your approach to s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSolve it by using binary search on each row\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTraversing each row from bottom and check if the target lies in the range of the first and last element of ith row.If the target lies in the range then search for target using binary search.If found then return true.If not,then continue the traversing.If the last element of any row is found to be less than the target then break the loop and return false.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <iostream>\n#include <bits/stdc++.h>\nusing namespace std;\nclass Solution\n{\npublic:\n    bool searchMatrix(vector<vector<int>> &matrix, int target)\n    {\n        int row = matrix.size(), col = matrix[0].size();\n        for (int i = row - 1; i >= 0; i--)\n        {\n            if (matrix[i][0] <= target && target <= matrix[i][col - 1])\n            {\n                int r = col - 1, l = 0, mid;\n                while (l <= r)\n                {\n                    mid = (l + r) / 2;\n                    if (matrix[i][mid] == target)\n                    {\n                        return true;\n                    }\n                    else if (matrix[i][mid] < target)\n                    {\n                        l = mid + 1;\n                    }\n                    else\n                        r = mid - 1;\n                    ;\n                }\n            }\n            else if (target > matrix[i][col - 1])\n            {\n                break;\n            }\n        }\n        return false;\n    }\n};\n```
['C++']