看到有序+查找就想到二分，不过此题涉及二维查找，用线性搜索最快

方法一：暴力搜索，嵌套循环

• 时间复杂度O(M*N)

  public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[i].length;j++){
                if(array[i][j]==target)
                    return true;
            }
        }
        return false;
    }
  }

  方法二：二分查找

• 时间复杂度O(M*log(N))

  public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            if(biSearch(target,array[i])==target)
                return true;
        }
        return false;
    }
    private int biSearch(int target,int [] array){
        int start=0,end=array.length-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(array[mid]>target){
                end = mid-1;
            }else if(array[mid]<target){
                start = mid+1;
            }else{
                return array[mid];
            }
        }
        return -1;
    }
  }

  方法三：线性搜索

• 只能以左下角或者右上角为起点，否则无法根据大小选择下一步方向
• 时间复杂度O(M+N)

  public class Solution {
    public boolean Find(int target, int [][] array) {
        int i=array.length-1,j=0;
        while(i>-1&&j<array[i].length){
            if(array[i][j]==target)return true;//先判断，再移动ij
            if(array[i][j]>target){
                i--;
            }else if(array[i][j]<target){
                j++;
            }
        }
        return false;
    }
  }