二维数组中的查找

题目

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

分析

　　从二维数组的左下或右上开始查询，本题中将以左下为例。由于每行每列都是递增的，所以从左下角（i = row-1, j = 0）开始，当target<array[i][j]时，i--；当target>array[i][j]时，j++。直到满足临界条件，即target==array[i][j]或i<0或j>col-1时，返回判断值。

代码

 1 public boolean Find(int target, int [][] array) {
 2         
 3         int row = array.length, col = array[0].length;
 4                 if(row==0 || col==0)
 5                       return false;
 6         int i = row-1, j = 0, tag = 0;
 7         while(i>=0 && j<=col-1 && target!=array[i][j]){
 8             while(i>=0 && target<array[i][j]) i--;
 9             if(i<0){
10                 tag = 1;
11                 break;
12             }
13             while(j<=col-1 && target>array[i][j]) j++;
14             if(j>col-1){
15                 tag = 1;
16                 break;
17             }
18         }
19         if(tag == 0)
20             return true;
21         else
22             return false;
23     }