算法学习|【算法学习】二维数组查找（Java）算法|二维数组|二分查找|检索

一、题目描述此题源于《剑指 offer》

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

输入：
[
[1, 2, 8, 9],
[4, 7, 10, 13]
],7
输出： true

二、思路分析此题与前文二维数组检索 search-a-2d-matrix类似，与前文稍有不同，前文题目中每一行的第一个数字都比上一行最后一个数字大，这个条件保证了数组有序是单向的（此处的单向指的是一个方向的递增），但是此题难度稍微加剧，数组递增是向右向左递增，左右递增没有关系（可以理解为双向有序）。
解题技巧在于化双向为单向，如果同时考虑两个方向的递增那么必然会加大复杂度。可以采用从右上角或者左下角开始检索。以左上角为例，左上角具有当前行最大，当前列最小的特征，一定程度保证了单向，简化问题复杂度，以下是详细步骤

以左上角为起点，开始检索。
如果左上角元素大于目标元素，则目标元素定不存在当前列，起点右移。
如果左上角元素小于目标元素，则目标元素定不存在当前行，起点下移。
重复以上2，3步骤，最终可以将元素确定到一列或者一行中，此时可采用二分查找完成检索。

三、参考代码

public class Solution { public boolean Find(int target, int [][] array) { //步骤 1 int x = array[0].length - 1,y = 0; //步骤 2，3 while(x > 0 && y < (array.length - 1)){ if(array[y][x] == target) return true; if(array[y][x] < target) y++; if(array[y][x] > target) x--; } int mid,left,right; //步骤 4 if(x == 0){ left = y; right = array.length -1; while(left <= right){ mid = left + (right -left)/2; if(array[mid][0] == target) return true; if(array[mid][0] > target) right = mid - 1; if(array[mid][0] < target) left = mid + 1; } }else{ if(y == array.length - 1){ left = 0; right = x; while(left <= right){ mid = left + (right -left)/2; if(array[y][mid] == target) return true; if(array[y][mid] > target) right = mid - 1; if(array[y][mid] < target) left = mid + 1; } } } return false; } }

四、测试连接 【算法学习|【算法学习】二维数组查找（Java）】牛客网算法测试连接