|
| 1 | +package chapter2_binary_search; |
| 2 | + |
| 3 | +/**Write an efficient algorithm that searches for a value in an m x n matrix. |
| 4 | +
|
| 5 | +This matrix has the following properties: |
| 6 | +
|
| 7 | +Integers in each row are sorted from left to right. |
| 8 | +The first integer of each row is greater than the last integer of the previous row.*/ |
| 9 | +public class Searcha2DMatrix { |
| 10 | + //I'm so glad that I made it AC'ed the first time I submitted it, I really overcame my comfort zone to do this problem: |
| 11 | + //My comfort zone was to just binary search first column first, locate which row, then binary search that row. |
| 12 | + //Then I quickly pushed myself away from this comfort zone and challenged myself to do it using index/col, index%col as row and col indices |
| 13 | + //for a matrix, cheers! And it even got AC'ed the first time I submitted! |
| 14 | + |
| 15 | + /** |
| 16 | + * @param matrix, a list of lists of integers |
| 17 | + * @param target, an integer |
| 18 | + * @return a boolean, indicate whether matrix contains target |
| 19 | + */ |
| 20 | + public boolean searchMatrix(int[][] matrix, int target) { |
| 21 | + // write your code here |
| 22 | + if(matrix == null || matrix.length == 0) return false; |
| 23 | + if(matrix[0][0] > target || matrix[matrix.length-1][matrix[0].length-1] < target) return false; |
| 24 | + int height = matrix.length, width = matrix[0].length, len = height*width, start = 0, end = len-1; |
| 25 | + while(start+1 < end){ |
| 26 | + int mid = start + (end-start)/2; |
| 27 | + int row = mid/width, col = mid%width; |
| 28 | + if(matrix[row][col] == target) return true; |
| 29 | + else if(matrix[row][col] > target) end = mid; |
| 30 | + else start = mid; |
| 31 | + } |
| 32 | + if(matrix[start/width][start%width] == target || |
| 33 | + matrix[end/width][end%width] == target) return true; |
| 34 | + return false; |
| 35 | + } |
| 36 | + |
| 37 | + |
| 38 | +} |
0 commit comments