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.Example 1:
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true
题意：
给定2D Matrix, 从左至右，从上到下升序排列, 问2D Matrix中是否含有target
思路: Binary Search
题干说明了input有从左至右，从上到下升序排列，强暗示需要用Binary Search
需要注意：
int midValue = matrix[mid / n][mid % n];mid/n
可以得出mid在第几个n上，即Matrix的row
mid%n
可以得出mid在n的第几位上，即Matrix的col
代码
1 class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 if (matrix.length == 0) return false; 4 final int rowLen = matrix.length; 5 final int colLen = matrix[0].length; 6 7 int l = 0; 8 int r = rowLen * colLen -1 ; 9 10 while (l <= r) { 11 int mid = l + (r - l) / 2; 12 int midValue = matrix[mid / colLen][mid % colLen]; 13 14 if (midValue == target){ 15 return true; 16 } else if (midValue < target) { 17 l = mid + 1; 18 } else{ 19 r = mid -1; 20 } 21 } 22 return false; 23 } 24 }
转载于:https://www.cnblogs.com/liuliu5151/p/10953136.html
