二维数组中的查找 - Java版 -简单二分查找 -<<剑指Offer>> -水题

时间:2022-07-02 15:08:13

如题 (总结)

-认真读题, 还WA了一次,

借鉴学习文章列表

  • 链接1:
  • 链接2:
  • ALiBaBaJavaCodingGuideLines

1.问题

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

2. 代码

/**
*在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,
* 每一列都按照从上到下递增的顺序排序。
* 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
* 比如3*3的矩阵:
* 1 2 3
* 2 3 4
* 3 4 55
* @author szs
*/
public class Solution {
public boolean Find(int target, int [][] array) {
int width = array[0].length;
int height = array.length; // int line = binaryIncludeFind(array,0,height-1,target,width);
int line;
for( line=0; line<= height-1;line++){
boolean ans= binaryEqualFind(array[line],0 , width-1 ,target );
if(ans)return true;
}
return false;
} /**
* @description 二分查找某个值是否在某行,饭后是/否
* @author SongZeShan
* @date 2019/7/10 16:38
* @param
* @return
*/
private boolean binaryEqualFind(int[] array,int low,int high,int val){
if(low>high){
return false;
}
if(val<array[low] || val>array[high]){
return false;
}else{
int mid = (low+high)/2;
if(array[low]<=val && array[mid]>val){
return binaryEqualFind(array, low, mid-1, val);
}else if(array[mid]==val){
return true;
}else{
return binaryEqualFind(array, mid+1, high, val);
}
}
}
}

3.测试类

/**
* FileName: ${FILENAME}
* 类的详细说明
*
* @author SongZeShan
* @version 1.0
* @Date 2019/7/10 16:33
*/
public class Test {
public static void main(String[] args) {
int arr[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}} ;
Solution solution = new Solution();
for(int i=1;i<=6;i++)
System.out.println(solution.Find(i, arr));
}
}

测试结果


true
true
false
true
false
true Process finished with exit code 0