剑指 Offer 04 二维数组中的查找

[GuoLizhi]

1. 二分查找+剪枝

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function(matrix, target) {
    const row = matrix.length;
    if (row === 0) return false;
    const col = matrix[0].length;

    for (let i = 0; i < row; i++) {
        if (matrix[i][col - 1] < target) continue;
        if (matrix[i][0] > target) return false;
        if (binarySearch(matrix[i], target)) {
            return true;
        }
    }

    return false;
};
var binarySearch = function (nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            return true;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return false;
}

2. 从右上角开始二分查找

var findNumberIn2DArray = function(matrix, target) {
    // 从整个矩阵右上角来看，是一棵二分搜索树
    // 如果当前位置的元素比target大，则col--
    // 如果当前位置的元素比target小，则row++
    // 如果相等则返回true
    // 如果越界了还没找到则返回false
    if (matrix.length === 0) return false;
    let row = matrix.length;
    let col = matrix[0].length;
    let currRow = 0;
    let currCol = col - 1;
    while (currRow < row && currCol >= 0) {
        if (matrix[currRow][currCol] === target) {
            return true;
        } else if (matrix[currRow][currCol] > target) {
            currCol--;
        } else {
            currRow++;
        }
    }
    return false;
};