Write an efficient algorithm to determine whether there is a target value in an M x n matrix. The matrix has the following characteristics:

The integers in each row are arranged in ascending order from left to right. The first integer in each line is greater than the last integer in the previous line.

Example 1:

Input: matrix = [[1.3.5.7], [10.11.16.20], [23.30.34.60]], target = 3Output:true
Copy the code

Example 2:

Input: matrix = [[1.3.5.7], [10.11.16.20], [23.30.34.60]], target = 13Output:false
Copy the code

Tip:

    m == matrix.length
    n == matrix[i].length
    1 <= m, n <= 100
    -104 <= matrix[i][j], target <= 104
Copy the code

Javascript violent solution

/ * * *@param {number[][]} matrix
 * @param {number} target
 * @return {boolean}* /
 var searchMatrix = function(matrix, target) {
    for(let i=0; i<matrix.length; i++){for(let j=0; j<matrix[0].length; j++){if(matrix[i][j]===target){
                return true}}}return false
};
Copy the code

Javascript array lookup

/ * * *@param {number[][]} matrix
 * @param {number} target
 * @return {boolean}* /
/* Use the lower left corner of the two-dimensional array as the origin of the rectangular axis. If the current number is greater than the search number, the search moves up one bit. If the current number is less than the search number, the search is moved one bit to the right. * /
 var searchMatrix = function(matrix, target) {
    let x = matrix.length-1,y = 0
    while(x>=0 && y<matrix[0].length){
        if(matrix[x][y]===target){
            return true
        }else if(matrix[x][y]>target){
            x--
        }else{
            y++
        }
    }
    return false
};
Copy the code

Javascript dichotomy

/ * * *@param {number[][]} matrix
 * @param {number} target
 * @return {boolean}* /
 var searchMatrix = function(matrix, target) {
    let m = matrix.length,n=matrix[0].length
    let low = 0,high = m*n-1
    while(low<=high){
        let mid = Math.floor((high-low)/2)+low / / the median
        let x = matrix[Math.floor(mid/n)][mid%n] // The value where
        if(x<target){
            low = mid+1
        }else if(x>target){
            high = mid-1
        }else{
            return true}}return false
};
Copy the code

Both types of Typescript can also be changed to TS

function searchMatrix(matrix: number[][], target: number) :boolean {
    let x: number = matrix.length - 1.y:number = 0
    while (x >= 0 && y < matrix[0].length) {
        if (matrix[x][y] === target) {
            return true
        } else if (matrix[x][y] > target) {
            x--
        } else {
            y++
        }
    }
    return false
};
Copy the code

Python brute force solution

class Solution(object) :def searchMatrix(self.matrix.target) :for i in range(len(matrix)) :for j in range(len(matrix[0])) :if matrix[i] [j]==target:
                    return True
        return False
Copy the code

Python any function

The any() function checks whether a given iterable argument is all False, and returns False, or True if any of the iterable arguments is True. Elements count TRUE except for 0, null, and FALSE.

grammar

def any(可迭代) :
    for element in iterable:
        if element:
            return True
    return False
Copy the code

solution

class Solution(object) :
     def searchMatrix(self, matrix, target) :
        return any(target in row for row in matrix)
Copy the code

Go array lookup

func searchMatrix(matrix [][]int, target int) bool {
	m := len(matrix)
	n := len(matrix[0])
	var i = 0
	for i < m && n > 0 {
		if target == matrix[i][n- 1] {
			return true
		} else if target < matrix[i][n- 1] {
			n--
		} else {
			i++
		}
	}
	return false
}
Copy the code
Try to solve a problem in four languages for the first time. Keep going!