搜索二维矩阵

问题链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

一、问题描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
 

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

 

二、问题分析

　　根据题目给出的二维数组特点可以看出这个数组是有序的，如果类比一维有序数组中的查找，可以想到二分法。但是怎么对二维数组进行二分就很不容易想，先分析一下数据结构，对于整个矩阵中的子矩阵，可以看出子矩阵最右下角元素的值的整个矩阵的最大值，相应的，左上角的值是该子矩阵的最小值，这个性质很容易验证，只需要结合题目给出的矩阵的规则就不难验证。

　　既然已经知到一个矩阵中最小值在左上角，最大值在右上角，就应该运用这个性质，我们可以不断的压缩整个数组，当遍历到某个值时，如果该值大于目标值，那么我们可以保证该元素的下方和右方，不包含目标元素，同样的如果当前值比目标值小，所以以该节点为界，节点左上方的空间不包含目标元素。

　　根据上文推断出的两个性质，我们可以对数组中的节点进行判断，而且每次判断都对数组进行逻辑上的压缩（即不需要再遍历某些节点）。

　　出发点的选择，我们需要排除的元素是当前元素的左上方或右下方，如果从整个矩阵的左上方出发，当下移指针的时候就新添加了某些节点，但是就不能判断这些节点中有没有要找的元素，如果从左下方和右上方出发，因为该处节点必定时一列（一行）中的最大值，那么就可以确定该行或该列中有没有目标元素。

　　通俗来讲，如果从左上角或右下角出发实际上不是在压缩数组，而是在不断往数组中添加新元素，而从左下角或右上角，因为该处节点已经是一列或者一行中的最大值，同时又是一行或一列的最小值，就很容易对目标值进行判断（实际压缩了数组）

　　

 

 

 

 三、算法实现

　　代码：

 1 class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         int m = matrix.length;//m为行数
 4         int n = matrix[0].length;//n为列数
 5         int i = m-1;//i定义为指针行下标，j为指针列下标，从左下角开始遍历
 6         int j = 0;
 7         while(i>=0 && j<n){
 8             if(matrix[i][j] == target){
 9                 return true;
10             }else if(matrix[i][j] > target){
11                 i--;
12             }else if(matrix[i][j] < target){
13                 j++;
14             }
15         }
16         return false;
17     }
18 }