[leetcode]74. Search a 2D Matrix -- JavaScript 代码-蒲公英云

[leetcode]74. Search a 2D Matrix -- JavaScript 代码

朱雀 2022-07-19 11:52 131阅读 0赞

这道题很明显的就是用二分法，但是是两个维度的二分法：
第一次使用二分法，是要找到那个可能包含target数字的数组。也就是说，这个数组的第一个数应该小于target而它的下一个数组的第一个数要大于target。
第二次使用二分法就是在数组内寻找。这一步就是中规中矩的二分法了。
代码如下：

/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */
var searchMatrix = function(matrix, target) {
    var m_len = matrix.length;
    if(m_len>0){
        r_len = matrix[0].length;
    }
    if(m_len===0||r_len===0){
        return false;
    }
    var start = 0;
    var end = m_len-1;
    var mid = Math.floor((start + end)/2);
    while(start<end){
   // 第一次使用二分法，和正常的二分法稍有不同。
        if(matrix[mid][0]<target){
            start = mid+1>m_len-1?m_len-1:mid+1;
        }else if(matrix[mid][0]>target){
            end = mid-1<0?0:mid-1;
        }else{
            return true;
        }
        mid = Math.floor((start + end)/2);
    }
    var t_array = [];
    if(matrix[mid][0]>target){
        mid = mid-1<0?0:mid-1;
    }
    t_array = matrix[mid];
    start = 0;
    end = r_len-1;
    mid = Math.floor((start + end)/2);
    while(start<end){
   // 第二次使用二分法，就是中规中矩的二分法了。
        if(t_array[mid]<target){
            start = mid+1;
        }else if(t_array[mid]>target){
            end = mid-1;
        }else{
            return true;
        }
        mid = Math.floor((start + end)/2);
    }
    return (t_array[mid]==target);
};