二维数组中的查找

题目描述

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

思路

思路一：顺序遍历该二位数组依次比较大小，很显然该方法不可取；

思路二：由于数组每行都是递增的，因此对每行元素查找可以采用二分法，但是该思路并不是最优方法；

思路三：前两种思路都是从左上角元素出发，依次比较，如果换个思维从左下角或者右上角出发呢？从左下角出发，则当要查找数字比左下角数字大时右移，当要查找数字比左下角数字小时，上移，即可。代码如下：

public class Algorithm01 {

public static void main(String []args){

int [][]array = {
                {11,13,15,17,19},
                {21,23,25,27,29},
                {31,33,35,37,39},
                {41,43,45,47,49},
        };

        System.out.println(find(35, array));

    }


public static boolean find(int target, int [][] array) {
        boolean isFind = false;

if(array == null || array.length == 0 || array[0].length == 0){
return isFind;
        }

int lenI = array.length;        // 二维数组的行数
int lenJ = array[0].length;     // 二维数组的列数

int i=lenI-1, j=0;
do{

if(target == array[i][j]){
                isFind = true;
            }else if(target < array[i][j]){
                i--;
            }else{
                j++;
            }

        }while (i>=0 && j<lenJ && !isFind);

return  isFind;
    }
}