题目：搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

1、每行中的整数从左到右按升序排列。

2、每行的第一个整数大于前一行的最后一个整数。

例1：

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true

例2：

输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false

解读题目：

由题意可知，要是按照正常两个for循环嵌套输出此数组的话会得到一个递增的序列，且不会出现重复数字（因为条件2：每行的第一个整数大于前一行的最后一个整数）。因此，既然出现了一个排序后的递增序列就可以尝试使用二分法来找到target。

解法一：暴力法，即嵌套for循环遍历寻找

//1、暴力法 public static boolean searchMatrix(int[][] matrix, int target){ //判断要是matrix的长度要是为0就相当于matrix里什么元素都没有，直接返回false if(matrix.length == 0) return false; //嵌套for循环用来遍历每一个元素 for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[i].length; j++){ //要是在matrix里找到target那就直接返回true if(matrix[i][j] == target) return true; } } return false; }

暴力法的时间复杂度是O（m*n）

解法二：标准的二分法

依据题目意思，我们可以直接把一个二维的mn数组当做是一个长度为mn的一维数组，分别用“除以n”和“模n”来得到一维数组的位置里对应的二维数组的坐标，具体解法如下：

//2、二分法,把二维数组当做是一维数组来看待，关键的地方在于如何定位mid public static boolean searchMatrix(int[][] matrix, int target){ if(matrix.length == 0) return false; int m = matrix.length; int n = matrix[0].length; int left = 0; int right = m*n-1; while(left <= right){ int mid = left + ((right-left)>>1); //mid/n刚好可以知道元素在第几行,mid%n刚好可以知道在第几列 //这边要是不是很清楚就可以把例子遍历一下，自己计算看看 if(matrix[mid/n][mid%n] == target) return true; else if(matrix[mid/n][mid%n] > target) right = mid - 1; else left = mid + 1; } return false; }

二分法的时间复杂度O（log（m*n））

解法三：神奇的二分法

观察题目可以知道，上层元素小于下层元素，且相邻的右边元素大于左边元素，合起来就是相邻的两层里，右上角的元素总是小于其左下角的元素。这相当于是一个升序序列。所以有下面这个二分法的变式的解法：

//3、神奇的二分法 public static boolean searchMatrix(int[][] matrix, int target){ if(matrix.length == 0) return false; int row= 0;//行 int col = matrix[0].length-1;//列 //行是从0到matrix.length-1共matrix.length行 //列是从matrix[0].length-1到0共matrix[0].length列 while(row < matrix.length && col>= 0){//注意这边的边界值 //第一个元素值从左上角开始的 if(matrix[row][col] == target) return true; //如果比目标值大，则列左移，反之，行下移 else if(matrix[row][col] > target){ col--; } else row++; } return false; }

神奇二分法的时间复杂度O（log（m*n））

如果错误，欢迎评论，感谢指教。