二维数组中的查找【剑指offer——JAVA实现】

【考点：数组】二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

【初始】解法一：

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null) return false;
        
        int xLen = array[0].length;
        int yLen = array.length;
        
        if(xLen == 0 || yLen == 0) return false;
        
        for(int i = 0; i < yLen; i++) {
            if(array[i][xLen - 1] < target) continue; //如果该行最大值都小于目标值，跳过查询
            if(array[i][0] > target) break;   //纵坐标最小值已经大于目标值，说明没有找到，结束循环
            
            if(find(target, array[i], array[i].length - 1, 0))
                return true;
            else 
                continue;
        }
        
        return false;
    }
    
    //二分查找
    public boolean find(int target, int[] array, int high, int low) {
        int hi = high;
        int lo = low;
        
        if(hi < lo) return false;
        int mid = (hi + lo) / 2;
        
        if(target < array[mid]) return find(target, array, mid - 1, lo); 
        else if(target > array[mid]) return find(target, array, hi, mid + 1);
        else return true;
    }
    
}

分析：这个算法也就剔除了上面几行，然后开始用二分法对剩下的有可能出现值的每一行进行了查找，显得很生硬。

【改进】解法二：

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null) return false;
        //拿到列数
        int xLen = array[0].length;
        //拿到行数
        int yLen = array.length;
        //如果输入不合法 返回false
        if(xLen == 0 || yLen == 0) return false;
        //解题思路：
        //1.每次选取右上角的数num = array[y][x]
        //2.如果该数大于target，则当前列无效（当前列下方的元素肯定大于target） num = array[y][--x];
        //3.如果该数小于target，则当前行无效（当前行左边的元素肯定小于target） num = array[++y][x];
        //4.如果该数等于target，则返回，跳出循环
        
        //初始化
        int row = 0;
        int column = xLen - 1; //注意： 需要xLen - 1，不然会数组越界
        
        //标志位
        boolean found = false;
        
        while(row < yLen - 1 && column >= 0) { //注意： 需要yLen - 1，不然会数组越界
            if(array[row][column] == target) {
                found = true;
                break;
            }else if(array[row][column] > target) {
                column--;
            }else{
                row++;
            }
        }
        return found;
    }
}

分析：逻辑条理非常清晰

更多算法解答请点击《剑指offer》66题JAVA代码算法实现全集