Search a 2D Matrix

Link

https://leetcode.com/problems/search-a-2d-matrix/

Deadline

Mar 22, 2022

Status

Archived

Type

Binary Search

Matrix

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.

은찬


/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    for(let i = 0; i < m; i++){
        const front = matrix[i][0];
        const back = matrix[i][n - 1];
        
        if(target >= front && target <= back){
            let frontIndex = 0;
            let backIndex = n;
            
            while(frontIndex <= backIndex){
                const mid = Math.floor((frontIndex + backIndex) / 2);
                const cmp = matrix[i][mid];
                
                if(cmp === target){
                    return true;
                } else if(cmp > target){
                    backIndex = mid - 1;
                } else{
                    frontIndex = mid + 1;
                }
            }
        }
    }
    
    return false;
};

재영

앗... 야... 야매로 풀어써오...

~~이건 못참치~~...😅

64 ms, faster than 85.66%


/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
const searchMatrix = (matrix, target) => {
    return matrix.flat().indexOf(target) !== -1;
};

효성


var searchMatrix = function(matrix, target) {
    const arr = [];
    const m = matrix.length, n = matrix[0].length;
    
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            arr.push(matrix[i][j]);
        }
    }
    
    let low = 0, high = arr.length - 1, mid;
    
    while(low <= high) {
        mid = parseInt((low + high) / 2);
        
        if(arr[mid] === target) return true;
        else if(arr[mid] > target) high = mid - 1;
        else low = mid + 1;
    }
    
    return false;
};