mysql查询二维数组_[剑指offer]二维数组中的查找

二维数组中的查找

题目描述

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

例如&＃xff1a;下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7&＃xff0c;则返回true&＃xff1b;如果查找数字5&＃xff0c;由于数组不含有该数字&＃xff0c;则返回false。

思路1

观察特点&＃xff0c;以左下角元素为起点&＃xff0c;上方的元素都比这个数小&＃xff0c;右边的元素都比这个数大。所以如果target与array[i][j]比较的三种形式

相等&＃xff0c;true

小于&＃xff0c;i--&＃xff0c;往上方元素找

大于&＃xff0c;j&＃43;&＃43;&＃xff0c;往右方元素找

类似的可以推出起点在右上角的情况&＃xff0c;主要是通过区分一大一小可以确定下一个比较元素的大致寻找方向。左下角为起点的代码如下

public class Solution {

public boolean Find(int target, int [][] array) {

int rows &＃61; array.length;

int cols &＃61; array[0].length;

int i &＃61; rows - 1,j &＃61; 0;

while(i >&＃61; 0 && j

if(target &＃61;&＃61; array[i][j])

return true;

if(target

i--;

continue;

}

if(target > array[i][j]){

j&＃43;&＃43;;

continue;

}

}

return false;

}

}

思路2

对每一行进行二分查找&＃xff0c;逐行进行遍历

public class Solution {

public boolean Find(int target, int [][] array) {

int rows &＃61; array.length;

int cols &＃61; array[0].length;

for(int i &＃61; 0; i

int low &＃61; 0;

int high &＃61; cols - 1;

while(low <&＃61; high){

int mid &＃61; (low &＃43; high) / 2;

if(target

high &＃61; mid - 1;

else if(target > array[i][mid])

low &＃61; mid &＃43; 1;

else

return true;

}

}

return false;

}

}