二维数组中的查找

题目：

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

1, 2, 8, 9

2, 4, 9, 12

4, 7, 10, 13

6, 8, 11, 15

判断 7 所在位置

分析：

1. 首先想到的方法就是遍历这个二维数组，然后拿其中每一个数字和输入进行比较，如果存在一个数和输入相等，则输入数存在于这个二维数组中；

2. 从二维数组中选取右上角的数m来和输入数字n进行比较：

   • 如果m=n，则存在；
   • 如果m>n，则排除m所在列，因为m下面行所有数字都大于m；
   • 如果m<n，则排除m所在行，因为m左边所有数字都小于m。

   然后逐步缩小范围，查找出n所在位置。同理，也可以选择左下角的数字来进行比较判断。

   注意：不能选取左上角和右下角的数字，因为不能排除所在行和列缩小范围。

方案一实现：

public static boolean searchByIter(int[][] arr, int input) {
    if (null == arr || arr.length <= 0) {
        return false;
    }

    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if (input == arr[i][j]) {
                return true;
            }
        }
    }

    return false;
}

方案二实现：

public static boolean searchByExclude(int[][] arr, int input) {

    if (null == arr || arr.length <= 0) {
        return false;
    }

    // 行数
    int rows = arr.length;
    // 列数
    int columns = 0;

    for (int[] innerArr : arr) {
        columns = innerArr.length > columns ? innerArr.length : columns;
    }

    int row = 0;
    int column = columns - 1;
    while (row < rows && column > 0) {
        if (arr[row][column] == input) {
            return true;
        } else if (arr[row][column] > input) {
            --column;
        }else{
            ++row;
        }
    }

    return false;
}