240. Search a 2D Matrix II

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

Question

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 in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

二分查找

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    const binarySearch = (nums, target) => {
        if (!nums.length) return false;
        let left = 0;
        let right = nums.length - 1;
        // <= 保证 [n, n]这个区间是被考虑进去的
        while (left <= right) {
            const mid = ~~((left + right) / 2);
            if (nums[mid] === target) return true;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    };
    for (let i = 0; i < matrix.length; i++) {
        const exist = binarySearch(matrix[i], target);
        if (exist) return true;
    }
    return false;
};

End

是有序数组，可以优先想到二分查找。

而且二分查找是可能比自带的sort/find效率要更高的，因为这些是通用的方法，而二分查找是专门针对有序数组的。