数组--二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例
输入数组：
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
如果输入查找数值为7，则返回true，
如果输入查找数值为5，则返回false。
代码格式要求
public class Solution {
public boolean Find(int target, int [][] array) {
}
}
解题
一、暴力法
思路-直接遍历数组
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i=0;i<array.length;i++){ //array.length表示数组的行数
for(int j=0;j<array[0].length;j++){ //array[0].length表示数组指定行的列数
if(array[i][j]==target){
return true;
}
}
}
return false;
}
// 测试
public static void main(String[] args){
Solution a=new Solution();
int b[][]={ { 1, 2, 4, 5 }, { 3, 4, 9, 12 }, { 4, 8, 10, 13 }, { 6, 14, 15, 16 } };
boolean x=a.Find(8,b);
System.out.println("x:"+x);
}
}
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)
二、右上角法
1.思路
首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
2、举例
过程如下：
3.代码
public class Solution {
public boolean Find(int target, int [][] array) {
//判断边界条件
if(array==null||array[0]==null||array.length==0||array[0].length==0)
return false;
//获取矩阵的行数m，列数n
int m=array.length,n=array[0].length;
//初始化一开始元素的位置（这里设置右上角）
int i=0,j=n-1;
//循环遍历整个函数
while(i<m&&j>=0) {
if(target>array[i][j]) //如果目标值大于右上角的数字消去第一行i++
i++;
else if(target<array[i][j]) //如果目标值小于右上角的数字消去最后一列j--
j--;
else return true; //如果相等返回true
}
return false;
}
public static void main(String[] args){
Solution mm=new Solution();
int a[][]={ { 1, 2, 4, 5 }, { 3, 4, 9, 12 }, { 4, 8, 10, 13 }, { 6, 14, 15, 16 } };
boolean x=mm.Find(8,a);
System.out.println("x:"+x);
}
}
4.复杂度分析
时间复杂度：O(n+m) 。在循环语句中，除非直接返回结果，否则每一次行都会递减一次或者列都会递增一次。该矩阵共有 m 行 n 列，因此循环终止之前，循环不会运行超过 n+m 次。其它的操作都是常数，所以总的时间复杂度是线性的。
空间复杂度：O(1)。没有使用额外的存储空间，所以它的内存占用是恒定的。
三、二分查找
二分查找的条件是对一组有序数组的查找；在使用二分查找的时候先要对数组进行排序。
1.思路
思路：一个有序数组，想要查找一个数字key的下标，首先算出中间下标mid，利用mid把这个数组分为两半，前一半从下标0到mid-1，后一半从mid+1到数组最后一个元素（下标是数组长度减一）。把这个查找的元素key和数组下标为mid的元素进行比较，也就是和中间那个元素进行比较，如果比这个元素的小那么把查找范围缩小到原数组的前一半（把查找下标缩短到0到mid-1），如果比中间mid下标元素大那么范围就是后半部分（下标为mid+1到数组长度减一），这样来回反复取中间比较最后就会定位到要查找元素key的下标。
2.代码
public boolean Find(int target, int [][] array)
{//判断边界条件
if(array==null||array[0]==null||array.length==0||array[0].length==0)
return false;
//循环遍历整个函数
for(int i=0;i<array.length;i++)
{ //获取矩阵下标的最小值low，最大值为high
int low=0,high=array[i].length-1;
while(low<=high)
{int mid=(low+high)/2;
if (target<array[i][mid])
high=mid-1;
else if(target>array[i][mid])
low=mid+1;
else
return true;
}
}
return false;
}
