前言

剑指offer是非常经典的算法面试题，之前在牛客网上做过一遍，现在做第二遍并且分析记录。博客中还会出现数据结构和经典算法的篇幅，但是剑指offer单独拿出来，总共60多个题，分析一下，到时候也可以给师弟网友学习过程中作为参考。我自己也能熟悉面试题，巩固算法知识，保持编程状态。

二维数组中的查找

题目

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

分析

遍历数组能解决问题，但是由于所给数组已经部分排序，我们可以利用这个排序规则进行不必要的比较剔除，进行优化。试想如果起点是左下角，同目标值比较，如果大于目标值，整行我们就不用比较了，如果小于目标值，本行之前也都不用比较了。

实现

以右上角为起点，代码如下：

public boolean Find(int target, int [][] a) {
    // 右上角初始值，第一行最后一列。
    int j=a[0].length-1;
    int i=0;
    //循环条件
    while((j>=0)&&i<a.length){
        //大于目标值，该行之后肯定都大于目标值，只会在该行，减少列数查找
        if(a[i][j]>target)
            --j;
        //小于目标指，则该行全小于目标值，往下一行查找
        else if(a[i][j]<target)
            ++i;
        //相等返回true
        else
            return true;
    }
    //循环结束还未返回true，则返回false。
    return false;
}

以左下角为起点，代码如下：

    public boolean Find(int target, int [][] a) {
    //左下角初始值，最后一行，第一列
    int i=a.length-1;
    int j=0;
    //循环条件
    while((i>=0)&&j<a[0].length){
        //大于目标值则该行都大于目标值，往上一行查找。
        if(a[i][j]>target)
            --i;
        //小于目标值，则该行之前都小于目标值，结果只会在该行，再增加列数查找
        else if(a[i][j]<target)
            ++j;
        //相等返回true
        else
            return true;
    }
    //循环结束还未返回true，则返回false。
    return false;
}