剑指Offer——二维数组中的查找

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

leetcode类似

这个题目跟leetcode的题目不太一样，做法也不一样。leetcode 上说明了下一行的第一个数字一定大于上一行的最后一个数字，所以分别对行和列做二分就行，而本题不行

• 方法一，每一个行和列都做二分

 public boolean Find(int target, int[][] array) {
        for (int row = 0; row < array.length; row++) {
            int left = 0, right = array[row].length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (array[row][mid] == target) {
                    return true;
                }

                if (array[row][mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }

• 方法二：从二维数组的左下角(i,j)开始找，num[i-1,j]一定小于num[i,j],num[i,j+1]一定大于num[i,j]

public boolean Find2(int target, int[][] array) {
        int i = array.length - 1;
        int j = 0;
        while ((i >= 0) && (j <= array[0].length - 1)) {
            if (array[i][j] == target) {
                return true;
            }

            if (array[i][j] < target) {
                j++;
                continue;
            }

            if (array[i][j] > target) {
                i--;
                continue;
            }
        }
        return false;
    }