题目：
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.
解题思路：利用两次二分查找法。因为所给矩阵第一列也是升序排列的，所以可以先对第一列进行二分查找，锁定该元素所在行数，然后再对列进行二分查找，即可判断target是否存在。这个的算法时间复杂度是O(log(rows)+log(columns))。
代码：
1 /** 2 * 本代码由九章算法编辑提供。没有版权欢迎转发。 3 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。 4 * - 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班 5 * - 更多详情请见官方网站：http://www.jiuzhang.com/ 6 */ 7 8 // Binary Search Twice 9 public class Solution { 10 public boolean searchMatrix(int[][] matrix, int target) { 11 if (matrix == null || matrix.length == 0) { 12 return false; 13 } 14 if (matrix[0] == null || matrix[0].length == 0) { 15 return false; 16 } 17 18 int row = matrix.length; 19 int column = matrix[0].length; 20 21 // find the row index, the last number <= target 22 int start = 0, end = row - 1; 23 while (start + 1 < end) { 24 int mid = start + (end - start) / 2; 25 if (matrix[mid][0] == target) { 26 return true; 27 } else if (matrix[mid][0] < target) { 28 start = mid; 29 } else { 30 end = mid; 31 } 32 } 33 if (matrix[end][0] <= target) { 34 row = end; 35 } else if (matrix[start][0] <= target) { 36 row = start; 37 } else { 38 return false; 39 } 40 41 // find the column index, the number equal to target 42 start = 0; 43 end = column - 1; 44 while (start + 1 < end) { 45 int mid = start + (end - start) / 2; 46 if (matrix[row][mid] == target) { 47 return true; 48 } else if (matrix[row][mid] < target) { 49 start = mid; 50 } else { 51 end = mid; 52 } 53 } 54 if (matrix[row][start] == target) { 55 return true; 56 } else if (matrix[row][end] == target) { 57 return true; 58 } 59 return false; 60 } 61 } 62 63 // Binary Search Once 64 public class Solution { 65 public boolean searchMatrix(int[][] matrix, int target) { 66 if (matrix == null || matrix.length == 0) { 67 return false; 68 } 69 if (matrix[0] == null || matrix[0].length == 0) { 70 return false; 71 } 72 73 int row = matrix.length, column = matrix[0].length; 74 int start = 0, end = row * column - 1; 75 76 while (start + 1 < end) { 77 int mid = start + (end - start) / 2; 78 int number = matrix[mid / column][mid % column]; 79 if (number == target) { 80 return true; 81 } else if (number < target) { 82 start = mid; 83 } else { 84 end = mid; 85 } 86 } 87 88 if (matrix[start / column][start % column] == target) { 89 return true; 90 } else if (matrix[end / column][end % column] == target) { 91 return true; 92 } 93 94 return false; 95 } 96 }
转载于:https://www.cnblogs.com/hygeia/p/4651751.html
