算法练习：查找二维数组中的目标值

题目：

• 编写一个高效的算法来搜索矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

实现：

1. main方法

public static void main(String[] args) {int[][] 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}};// 方式一：暴力破解boolean b = method1(matrix, 5);System.out.println(b);// 方式二：二叉树原理查找method2(matrix, 5);
}

2. 方式一：暴力破解（不推荐）

/*** 方式一：暴力破解* @param matrix* @param i*/private static boolean method1 ( int[][] matrix, int i){// 方式一：暴力破解// 遍历矩阵，找到对应元素即可,不推荐：时间复杂度O(n^2)int row = matrix.length;int col = matrix[0].length;for (int j = 0; j < row; j++) {for (int k = 0; k < col; k++) {if (matrix[j][k] == i) {System.out.println("way1: {" + j + "," + k + "}");return true;}}}return false;}
}

3. 方式二： 二叉树原理查找

 /*** 方式二：二叉树原理查找** @param matrix* @param target*/
private static boolean method2(int[][] matrix, int target) {// 方式二：二叉树原理查找// 从左下角开始查找，如果当前元素大于目标值，则向上查找，如果当前元素小于目标值，则向右查找// 时间复杂度：O(m+n)int row = matrix.length - 1; // 行int col = 0; // 列while (col < matrix[0].length && row >= 0) {// 相等则返回if (matrix[row][col] == target) {System.out.println("way2: {" + row + "," + col + "}");return true;} else if (matrix[row][col] > target) { // 如果当前元素大于目标值，则向上查找row--;} else if (matrix[row][col] < target) { // 如果当前元素小于目标值，则向右查找col++;}}return false;
}