二维数组的查找问题

问题描述：给定一个二维整数数组，其中每一行从小到大排列，每一列也是从小到大排列，给定一个整数，判断该数是否在该数组中。

分析：对于干问题，最简答的方法就是穷举了，但是时间复杂度太高了，这时我们可以使用这个矩阵数组的特点来解决。

每行和每列元素都是从小到大排列，可以利用这个性质，我们可以从右上角或者左下角开始进行比较，也就是用反对角线上的元素进行比较，以右上角为例：

1.如果该数大于右上角元素，则可以排除右上角元素所在的列，下次向左搜索；

2. 如果该数小于右上角元素，则可以排除右上角元素所在的行，下次向下搜索；

3.如果该数等于右上角元素，则可以直接返回结果。

具体的Java代码如下，写法比较通用，读者可以很容易转换为其他语言实现。

 1 public class Main {
 2     public static boolean search(int a[][],int p){
 3         boolean flag=false;
 4         if(a==null)return flag;                    //如果是空数组则返回false
 5         int n1=a.length-1,n2=a[0].length-1;        //求出第一维和第二维的长度
 6         int i=0,j=n2;
 7         while(i<=n1 && j>=0){
 8             if(a[i][j]>p)j--;                      //删除列
 9             else if(a[i][j]<p)i++;                 //删除行
10             else  {flag=true;break;}               //找到元素
11         }
12         return flag;
13     }
14     public static void main(String[] args) {
15         // TODO 自动生成的方法存根
16         int a[][]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
17         int p=8;
18         System.out.println(search(a,p));
19     }
20 
21 }

输出结果为：

true