题目出处
74-搜索二维矩阵-题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
74-搜索二维矩阵-官方解法
方法1：两次二分查找
思路：
代码示例：（Java）
public class Solution1 {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 low = -1, high = matrix.length - 1;while (low < high) {int mid = (high - low + 1) / 2 + low;if (matrix[mid][0] <= target) {low = mid;} else {high = mid - 1;}}return low;}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}}复杂度分析
方法2:一次二分查找
思路：
代码示例：（Java）
public class Solution2 {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}}
复杂度分析
结语
两种方法殊途同归，都利用了二分查找，在二维矩阵上寻找目标值。值得注意的是，若二维数组中的一维数组的元素个数不一，方法二将会失效，而方法一则能正确处理。
考察知识点
收获
Gitee源码位置
74-搜索二维矩阵-源码
