HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Search a 2D Matrix

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.
notion image
은찬
재영
앗... 야... 야매로 풀어써오...
이건 못참치...😅
64 ms, faster than 85.66%
효성
 
/**
 * @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;
};
/**
 * @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;
};