[LeetCode 74]Search a 2D Matrix

题目链接：search-a-2d-matrix

/** * Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of the previous row.For example,Consider the following matrix:[[1, 3, 5, 7],[10, 11, 16, 20],[23, 30, 34, 50]]Given target = 3, return true. * */public class SearchA2DMatrix {//134 / 134 test cases passed.//Status: Accepted//Runtime: 236 ms//Submitted: 0 minutes ago//时间复杂度 O(log(max(m,n)) 空间复杂度 O(1)static boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length; //行数int n = matrix[0].length;//列数int up = 0;int down = m – 1;int left = 0;int right = n;//二分法查找所在行while(up < down) {int mid = (down + up) / 2;if(matrix[mid][n – 1] > target) down = mid;else if(matrix[mid][n – 1] < target) up = mid + 1;else return true;}//二分法查找所在列while(left < right) {int mid = (left + right) / 2;if(matrix[up][mid] > target) right = mid;else if(matrix[up][mid] < target) left = mid + 1;else return true;}return false;}public static void main(String[] args) {System.out.println(searchMatrix(new int[][]{{1, 3, 5, 7},{10, 11, 16, 20},{23, 30, 34, 50}}, 3));System.out.println(searchMatrix(new int[][]{{1, 1}}, 2));System.out.println(searchMatrix(new int[][]{{1,}, { 3}}, 2));System.out.println(searchMatrix(new int[][]{{1}}, 1));}}

，愈想得到，就愈要放手。放手是很难的，但是别无选择。