题解 | #二维数组中的查找#

因为二维数组中数的分布是同一列上由上而下数从小到大排列，同一行上由左到右数从小到大排列，从左下角位置开始查找，如果当前数小于target说明target可能在当前数的右方或者右上方位置（肯定不在当前列了，因为当前数是这列最大的数了），所以向右移动一位，如果当前数大于target，说明target可能在当前数的上方或者上右方位置（肯定不在当前行，因为当前数是这行中最小的数），所以向上移动一位。时间复杂度为O(m+n)

public class Solution {
    public boolean Find(int target, int [][] array) {
        // 从左下角开始找，如果target大于左下角的数，则往右移动
        // 如果小于的话则往上移动
        if(array.length < 1 || array[0].length < 1)
            return false;
        int x = array.length-1;
        int y = 0;
        
        while(x >= 0 && y<array[0].length){
            int temp = array[x][y];
            if(temp == target)
                return true;
            else if(temp < target) // 当前数小于target 向右移动
                y++;
            else  // 当前数大于target向上移动
                x--;
        }
        return false;
    }
}