剑指offer：二维数组中的查找-蒲公英云

剑指offer：二维数组中的查找

迷南。 2022-09-10 04:12 145阅读 0赞

描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。

给定 target = 3，返回 false。

输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
说明：
存在7，返回true

方法1，采用暴力破解，二维数组的遍历：

public class Solution { 
    public boolean Find(int target, int [][] array) { 
        for(int i=0;i<array.length;i++){ 
            for(int j=0;j<array[i].length;j++){ 
                if(array[i][j]==target){ 
                    return true;
                }
            }
        }
        return false;
    }
}

方法2：因为每一行都是有序数组，对每一行采用二分查找：
这里需要注意mid的定义和使用,mid在使用的时候,要low+(high-low)/2;因为如果使用(low+high)/2,会发生内存溢出.同时mid的位置应该放在while(low<high)的循环体之内

public class Solution { 
    public boolean Find(int target, int [][] array) { 
        for(int i=0;i<array.length;i++){ 
            int low=0;
            int high=array[i].length-1;
            while(low<=high){ 
                int mid=(low+high)/2;
                if(target>array[i][mid]){ 
                    low=mid+1;
                }else if(target<array[i][mid]){ 
                    high=mid-1;
                }else{ 
                    return true;
                }
            }
        }
        return false;
    }
}

方法三：取数组的右上角元素，如果当前target值大于该元素，说明target位于下一行，row++，如果当前target小于该元素，col–；

public class Solution { 
    public boolean Find(int target, int [][] array) { 
        int row=0;
        int col=array[0].length-1;
        while(row<array.length && col>=0){ 
            if(array[row][col]<target){ 
                row++;
            }else if(array[row][col]>target){ 
                col--;
            }else{ 
                return true;
            }
        }
        return false;
    }
}