搜索二维矩阵
题目链接：https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int l = 0, r = m - 1; int row = 0; //找到target可能所在的行 while(l <= r){ int mid = l + ((r - l) >>1); if(matrix[mid][0] <= target){ l = mid + 1; row = mid; } else{ r = mid - 1; } } l = 0; r = n-1; int col = 0; //在row行上查找target while(l <= r){ int mid = l + ((r - l) >>1); if(matrix[row][mid] <= target){ l = mid + 1; col = mid; } else{ r = mid - 1; } } return matrix[row][col] == target; }分析：代码的时间复杂度为O(logm + logn) = O(logmn)，空间复杂度为O(1)。解题思路：两次二分查找，先对二维矩阵的第一列进行一次二分查找，找到最后一个第一个数字小于等于target的行，然后在这行上再进行一次二分查找，寻找是否存在target。
看了官方题解后的解答：
//方法一：两次二分查找 //时间复杂度：O(logm+logn)=O(logmn) //空间复杂度：O(1) public boolean searchMatrix(int[][] matrix, int target) { int rowIndex = binarySearchFirstColumn(matrix, target); if(rowIndex < 0){ return false; } return binarySearchRow(matrix[rowIndex], target); } public int binarySearchFirstColumn(int[][] matrix, int target){ int l = -1, r = matrix.length - 1; while(l < r){ int mid = l + ((r - l + 1) >> 1);//为什么r-l还要加一？防止l = -1 且r = 0时的越界情况 if(matrix[mid][0] <= target){ l = mid; } else{ r = mid - 1; } } return l; } public boolean binarySearchRow(int[] row, int target){ int l = 0, r = row.length - 1; while(l <= r){ int mid = l + ((r - l) >> 1); if(row[mid] == target){ return true; } else if(row[mid] < target){ l = mid + 1; } else{ r = mid - 1; } } return false; } //方法二：一次二分查找 //时间复杂度：O(logmn) //空间复杂度：O(1) public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int l = 0, r = m * n - 1; while(l <= r){ int mid = l + ((r - l) >> 1); int x = matrix[mid / n][mid % n]; if(x == target){ return true; } else if(x < target){ l = mid + 1; } else{ r = mid - 1; } } return false; }分析：
1、方法一的解题思路与我的解答思路一致，只是实现上所有区别，具体区别请看代码。对于此方法，尤其要注意边界情况。
2、方法二的解题思路：根据题目，我们可以想象将每一行都拼接在上一行的末尾，这样我们就得到了一个一维的升序数组，我们可以在该数组上二分查找目标元素。代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。
总结
- 本题主要有两种方法解题，分别为两次二分查找、一次二分查找。主要还是需要掌握二分查找，并仔细分析边界情况。
