二维数组中查找某个数是否存在

题目很明了，给一个二位数组，二维数组从左到右逐渐增大，从上到下逐渐增大，再给一个要查找的数，判断数组里是否存在该数字。

最无脑的版本

下面的解法应该是排除直接双重循环之后最无脑的解法了，每次都先对一维数组进行判断，如果array[i][0] <= target && array[i][array[0].length - 1] >= target，就对这个数组进行一次遍历，查找目标数，如果存在返回true，否则进行下一次循环。

public static boolean Find(int target, int[][] array) {
        if (array == null) {
            return false;
        }
        if (array.length <= 0) {
            return false;
        }

        for (int i = 0; i < array.length; i++) {
            if (array[i][0] <= target && array[i][array[0].length - 1] >= target) {
                for (int j = 0; j < array[0].length; j++) {
                    if (target == array[i][j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

稍微动点脑子

上面的程序明显可以优化，最坏情况还是O(n^2)，即每个一维数组都符合if中的条件，从而进行一次查找。那么查找程序是否还可以优化呢，利用题目的条件：从左到右是递增的，那么利用二分查找可以将程序的最坏复杂度优化至O(nlogn)

if (array == null) {
            return false;
        }
        if (array.length == 0) {
            return false;
        }
        if (array[0].length <= 0) {
            return false;
        }

        for (int i = 0; array.length > 0 && i < array.length; i++) {
            if (array[i][0] <= target && array[i][array[0].length - 1] >= target) {
                int x = 0, y = array[0].length - 1, mid = (x + y) / 2;
                while (x <= y) {
                    if (array[i][mid] > target) {
                        y = mid - 1;
                        mid = (x + y) / 2;
                    } else if (array[i][mid] < target) {
                        x = mid + 1;
                        mid = (x + y) / 2;
                    } else {
                        return true;
                    }
                }
            }
        }
        return false;

更简单的方法

在讨论区找到了更简单的方法，通过从左下角开始搜索

public static boolean Find(int target, int[][] array) {
        int len = array.length - 1;
        int i = 0;
        while ((len >= 0) && (i < array[0].length)) {
            if (array[len][i] > target) {
                len--;
            } else if (array[len][i] < target) {
                i++;
            } else {
                return true;
            }
        }
        return false;
}

这种算法下如果是一个M x N的二维数组，复杂度为O(M + N)。同样的思路从右下角开始搜索也是可以的。