剑指offer-1-二维数组的查找

思路

• 数组指针移动，从0 0出发 （更好的思路是从0，n和n,0出发），根据状态移动
• 二份查找o(nlogn)，因为有内置函数，更快完成本题

踩坑：

对于数组 [[]] array.length=1 array[0]=0,所以二维数组判空条件不仅仅是 array.length<=0
实测没加 array==null也AC，保险起见加上，

代码

二分查找

//二分查找
import java.util.*;
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null || array.length<=0 || array[0].length<=0){
            return false;
        }
        for(int i=0;i<array.length;i++){
            if(Arrays.binarySearch(array[i],target)>=0){
                return true;
            }
        }
        return false;
    }
}

指针移动，根据状态移动

//从 0 0 出发 数组指针移动
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length<=0||array[0].length<=0){
            return false;
        }
        int p=0,q=0;// p行q列
        while(p<array.length && q<array.length){
            if(array[p][q]<target){ //状态 1
                //如果q+1大于tartget
                if(q==array[0].length-1 || array[p][q+1]>target){
                    p++;
                }else{
                    q++;
                }
            }else if(array[p][q]>target){ //状态 2
                if(q==0){
                    p++;
                }else{
                    q--;
                }
            }else{//状态 3
                return true;
            }
        }
        return false;
    }
}