74. Search a 2D Matrix

Leetcode

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

題目

Write an efficient algorithm that searches for a value in an m x n 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.

解答

• 方法一

因為是從左上到右下由小排到大，所以分別對列、欄進行二分搜尋法，找到最接近 target 的列、欄 index ，最後再回傳此值是否等於 target

var searchMatrix = function(matrix, target) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    let startRow = 0;
    let endRow = m - 1;
    while(startRow < endRow) {
        const mid = Math.ceil((startRow+endRow)/2);
        if(matrix[mid][0] > target) {
            endRow = mid - 1;
        } else {
            startRow = mid;
        }
    }
    
    let startCol = 0;
    let endCol = n - 1;
    while(startCol < endCol) {
        const mid = Math.ceil((startCol+endCol)/2);
        if(matrix[startRow][mid] > target) {
            endCol = mid - 1;
        } else {
            startCol = mid;
        }
    }
    return matrix[startRow][startCol] === target;
};

Runtime: 64 ms, faster than 98.25% of JavaScript online submissions for Search a 2D Matrix.

Memory Usage: 38.8 MB, less than 79.37% of JavaScript online submissions for Search a 2D Matrix.

測資

let matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3;
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13;

console.log(searchMatrix(matrix, target));