[JS] Search a 2D Matrix

🔒 문제 (LeetCode 74)

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.

Constraints:

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

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘 - 이분탐색

row 기준 이분탐색 : 가장 큰수를 이용하여 해당 row 찾기 -> column 기준 이분탐색으로 target 찾기

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let [rl, rr] = [0, matrix.length - 1];
    let [cl, cr] = [0, matrix[0].length - 1];
    
    while(rl < rr) {
        let mid = rl + rr >>> 1;
        if(matrix[mid][cr] < target) rl = mid + 1;
        else rr = mid;
    }
    
    if(matrix[rr][cl] === target) return true;
    
    while(cl < cr) {
        let mid = cl + cr >>> 1;
        if(matrix[rr][mid] < target) cl = mid + 1;
        else cr = mid;
    }
    

    if(matrix[rr][cr] === target) return true;

    return false;
};