面试题1：二维数组中查找

      《剑指offer》Java版代码全集：https://github.com/wuping5719/Algorithm/tree/master/1-Sword-Offer

      本题出自《剑指offer 名企面试官精讲典型编程题》面试题3。

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

      例如下面的二维数组就是每行每列递增排序。如果在数组中查询7，则返回true；如果查找数字14，由于数组中不包含14，则返回false。

      解决方法分析：

          首先我们选取二维数组左下角的数字8，由于8大于7，并且8还是第四行的第一个数，因此数字7不可能出现在8所在的行，于是我们把这一行从需要考虑的区域中剔除，之后需要分析的只剩下3行。在剩下的矩阵中，位于左下角的数字是4，4小于7，可以把4所在的列从需要考虑的区域中剔除。接下来只需要分析剩下的3行3列即可。同理，可以照之前处理方式继续处理。

      处理过程如下图所示：

              

           注：矩阵灰色区域为下一步要查找的范围，绿色为所要查找的数字。

      整个算法的逻辑：

        首先选取数组左下角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的行；如果该数字小于要查找的数字，剔除这个数字所在的列。也就是说，每次剔除一行或一列来缩小查找范围，直至找到要查找的数字，或者查找对应数字失败！

        当然除了选择左下角的数字外，也可以选择右上角的数字，查找方法类似。

        下面我以Java为编程语言，展示上述算法的处理过程。

package array;

/**
 * @author WuPing
 * @version 2016年4月7日 下午7:11:44
 */

public class FindInPartiallySortedMatrix {

    public static boolean FindNumber(int[] matrix, int rows, int columns,
        int number) {
    boolean found = false;
    if (matrix != null && rows > 0 && columns > 0) {
        //以二维数组左下角的数为查找比对标准
        int row = rows - 1;
        int column = 0;
        while (row >= 0 && column < columns) {
        if (matrix[row * columns + column] == number) {
            found = true;
            break;
        } else if (matrix[row * columns + column] > number) {
            --row;
        } else {
            ++column;
        }
        }
    }
    return found;
    }

    public static void Test(String testName, int[] matrix, int rows,
        int columns, int number, boolean expected) {
    if(testName != null) {
        System.out.print(testName + " begins: ");
        boolean result = FindNumber(matrix, rows, columns, number);
        if(result == expected) {
        System.out.print("Passed.");
            System.out.println();
        }
        else {
        System.out.print("Failed.");
            System.out.println();
        }
    }
    }
    
    public static void main(String[] args) {
    //此处以一维数组加行数和列数的形式表示二维数组
    int[] matrix = {1, 3, 6, 9, 2, 5, 7, 11, 4, 10, 13, 16, 8, 12, 15, 18};
    
    //要找的数在二维数组中，但不在左上角或右下角
    Test("Test1", matrix, 4, 4, 7, true);
    
    //要找的数不在二维数组中，但在数组范围内
    Test("Test2", matrix, 4, 4, 14, false);
    
    //要找的数在二维数组左上角
    Test("Test3", matrix, 4, 4, 1, true);
    
    //要找的数在二维数组右下角
    Test("Test4", matrix, 4, 4, 18, true);
    
    //要找的数在二维数组范围下界外
    Test("Test5", matrix, 4, 4, 0, false);
    
    //要找的数在二维数组范围上界外
    Test("Test6", matrix, 4, 4, 20, true);
    
    //传递的二维数组为空
    Test("Test7", null, 4, 4, 20, false);
    
    }

}

  代码执行结果如下：