【剑指offer】问题4：二维数组中的查找

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

先上代码。

public boolean Find(int target, int [][] array) {
        boolean ret = false;
        if(array == null)
            return ret;
        int rowNums = array.length;
        int colNums = array[0].length;

        int startRow = 0, startCol = colNums - 1;
        while(startRow < rowNums && startCol >=0){
            int tmp = array[startRow][startCol];
            if(tmp == target){
                ret = true;
                return ret;
            }else if(tmp > target){
                startCol --;
            }else{
                startRow ++;
            }
        }
        return ret;
    }

拿到这个题之后，很自然的想法就是从一个点开始遍历，遍历过程中将数组的值与target值进行比较，以此来决定下一步遍历的方向。假如我们从左上角的点开始遍历（这里说的左上角，是指的此二维数组表示出的矩阵），假如此值大于target，那么根据矩阵的特点可知，这个矩阵中的值都会比target大，因此二维数组中不存在target；如果此值小于target，那么target可能位于当前位置的右方、下方或者右下方，这样就看起来比较乱了。
我们重新选择一个起始位置：右上角。如果当前值大于target，那么说明当前值所在的列都大于target，要查找的值要么不存在，要么就在当前列的左边；如果当前值小于target，那么说明当前值所在的行都小于target，要查找的值要么不存在，要么就在当前行的下方。这样，不管当前值是大于还是小于target，当前指针都会只有一个移动方向，这样不断循环就能得到问题的解。

总结：上述分析过程的第一段，是初次拿到此题的心路历程，并未想到换一个启示位置和移动方向来考虑这个问题。后来就读到了书中的解题方式：从右上角或者左下角座位查询起始点。至于为什么会是右上角或者左下角呢？其实可以这么考虑：如何简洁、高效的移动指针应该是求解二维数组查找问题的关键。起始位置无非就是那四个，但是就此题来说，右上和左下具有这样的特点：该处的值是本行的最大值（最小值），却是本列的最小值（最大值）。这样无论当前值是大于还是小于target值，我总能有效的排除一整行或者一整列的值，并按照这个规律循环执行。左上和右下的值在本题中是不具备这样的优势的。
总结一条：还是要充分考虑数据结构的特点和数据的特性。遇到棘手的问题停滞不前时，可以尝试画图，从特殊例子出发寻找解决方案。从特殊到一般，本着这样的思路寻找解。