常见算法题：二维数组的查找

一、题目描述

一个二维数组，满足：每一行数字大小从左至右递增，每一列从上至下递增。求：一个函数，其满足输入一个二维数组与一个整数，判断数组是否含有该整数。

二、解决方法

• 1、最直接了当的方法

  function find(target, arr)
{
    let len=arr.length;
    for(let i=0;i<len;i++){
        for(let j=0;j<arr[i].length;j++){
            if(arr[i][j]==target)return true;
        }
    }
    return false;
}
缺点：时间复杂度为o(n2)，根据题设条件可以再优化

• 2、采用二分法

  function find(target,arr){
    for(let i=0;i<arr.length;i++){
        let low=0;
        let high=arr[i].length-1;
        while(low<=high){
            let mid=Math.round((high+low)/2);
            if(target<arr[i][mid])
                high=mid-1;
            else if (target>arr[i][mid])
                low=mid+1;
            else return true
        }
    }
    return false;
}
优点：时间复杂度o(nlog2n)，但比第一种方法稍复杂

• 3、根据题设采用边界判断方法

function find(target,arr){
    let m=arr.length;//行数
    let n=arr[0].length//列数
    let x=0;
    let y=m-1;//从最左下角树开始
    while(x<=n-1&&y>=0){//只要在边界内
        if (target<arr[y][x])
            y--;//上移
        else if (target>arr[y][x])
            x++;//右移
        else return true
    }
    return false;
}
优点：完整结合了题设条件，是较切合的解决方法

三、评论

查找效率一直是算法优化的重点问题，不同的算法，带来的消耗是不同的，要达到快准狠，是需要一番研究与实验的。