剑指offer算法-----数组遍历

积沙成塔

题目描述：

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

分析与实现：

在二位数组中查找一个数，我们可以一次遍历进行与目标数据比较得出，但这种方法的复杂度很大（n平方）。由于每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，所以当我们选择从二位数组的左下角开始查找遍历时，会大大降低算法复杂度(复杂度是n)。

从左下角开始查找的思路是：当目标数大于当前数时行不变，列增加1（此时只能是列加1，如果让行加1的话会在原地上下徘徊出现死循环），当目标数小于当前数时列不变行减一，搜索路径类似台阶，如下查找数字9的查找路线。

算法：

public class ArraySereach {
    public 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;
    }
}