剑指Offer_3_二维数组中的查找

2017-03-14

题目描述

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

解题思路
发现规律：

1.首先选取数组中右上角的数字。如果该数字等于key，查找过程结束
2.如果该数字大于key，则删除这个数字所在的列（因为该列所有元素都比key大）
3.如果该数字小于key，则删除这个数字所在的行（因为该行所有元素都比key小）

也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中删除一行或一列，
这样每一步都可以缩小查找范围，知道找到要查找的数字，或者查找范围为空。

代码实现

public class ArraySearch
{
    public static boolean findElementInArray(int[][] array, int key)
    {
        if (array == null)
            return false;
        int startCol = array[0].length - 1;
        for (int i = 0; i < array.length; i++)
        {
            for (int j = startCol; j > 0; j--)
            {
                System.out.println("查询位置:(" + i + "," + j + ")");
                // 如果当前数字大于key，则删除此列
                if (array[i][j] > key)
                {
                    // 删除过得列，不需要再查找，下次循环时从新的起始列开始查
                    startCol -= 1;
                    continue;
                }
                // 如果当前数字小于key，则删除此行
                else if (array[i][j] < key)
                    break;
                else
                {
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        //Integer[][] array = new Integer[row+1][col+1]; // 这里为什么要多一个 不然会报错？
        int[][] array = new int[][]{
                {1, 2, 8, 9},
                {2, 4, 9, 12},
                {4, 7, 10, 13},
                {6, 8, 11, 15}
        };
        for (int i = 0; i < array.length; i++)
        {
            for (int j = 0; j < array[i].length; j++)
            {
                System.out.print(array[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("===================");
        System.out.println("Result:" + findElementInArray(array, 15));
    }
}

补充
同样，我们可有选取左下角的数字。但是不能选择左上角和右上角，因为既不能删除行，也不能删除列。