Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:


	Integers in each row are sorted from left to right.
	The first integer of each row is greater than the last integer of the previous row.


&nbsp;
Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true


Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false


&nbsp;
Constraints:


	m == matrix.length
	n == matrix[i].length
	1 &lt;= m, n &lt;= 100
	-104 &lt;= matrix[i][j], target &lt;= 104


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left=0
        right=len(matrix)-1
        while left <= right:
            mid=(left+right)//2
            if matrix[mid][0] < target:
                left = mid+1
            elif matrix[mid][0] >target:
                right= mid-1
            else:
                return True
        left1=0
        right1=len(matrix[right])-1
        while left1 <= right1:
            mid=(left1+right1)//2
            if matrix[right][mid] < target:
                left1 = mid+1
            elif matrix[right][mid] >target:
                right1= mid-1
            else:
                return True
        return False
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (target < matrix[0][0]) {
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] > target | i == matrix.length - 1) {
                if (matrix[i][0] > target) {
                    i--;
                }
                for (int j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j] == target) {
                        return true;
                    }
                }
                return false;
            }
        }
        return false;
    }
}
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size(); i ++) {
            if(matrix[i][0] > target) return false;
            for(int j = 0; j < matrix[i].size(); j ++) {
                if(matrix[i][j] == target) return true;
                else if(matrix[i][j] > target) break;
            }
        }
        return false;
    }
};
var searchMatrix = function(matrix, target) {
    let matCopy = [...matrix];
    let leftIndex = 0;
    let rightIndex = matrix.length - 1;

    let mid = Math.ceil((matrix.length - 1) / 2);

    let eachMatrixLength = matrix[0].length;
  
    if (matrix[mid].includes(target) === true) {
        return true;
    } else if (matrix.length == 1) {
        return false;
    }

    if (matrix[mid][eachMatrixLength - 1] > target) {
        rightIndex = mid - 1;
        matCopy.splice(-mid);
    } else {
        leftIndex = mid + 1;
        matCopy.splice(0, mid);
    }

    return searchMatrix(matCopy, target);
   
};
Search a 2D Matrix