Sharing my concise C++ solution, using binary search, runtime 15 ms.


  • 0
    R
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size();
            int n = matrix[0].size();
            for (int i = 0; i < m; ++i){
                if (target>=matrix[i][0]&&target<=matrix[i][n-1])
                    return binarySearch(matrix[i], target);
                if (i>0&&target>matrix[i-1][n-1]&&target<matrix[i][0])
                    return false;
            }
            return false;
        }
        
        bool binarySearch(vector<int>& nums, int target){
            int len = nums.size();
            int left = 0, right = len-1;
            while(left <= right){
                int mid = (left+right)/2;
                if (nums[mid] == target)
                    return true;
                else if(nums[mid]<target)
                    left = mid+1;
                else
                    right = mid-1;
            }
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.