|
| 1 | +packagechapter2_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 | +publicclassSearcha2DMatrix { |
| 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 | +publicbooleansearchMatrix(int[][]matrix,inttarget) { |
| 21 | +// write your code here |
| 22 | +if(matrix ==null ||matrix.length ==0)returnfalse; |
| 23 | +if(matrix[0][0] >target ||matrix[matrix.length-1][matrix[0].length-1] <target)returnfalse; |
| 24 | +intheight =matrix.length,width =matrix[0].length,len =height*width,start =0,end =len-1; |
| 25 | +while(start+1 <end){ |
| 26 | +intmid =start + (end-start)/2; |
| 27 | +introw =mid/width,col =mid%width; |
| 28 | +if(matrix[row][col] ==target)returntrue; |
| 29 | +elseif(matrix[row][col] >target)end =mid; |
| 30 | +elsestart =mid; |
| 31 | + } |
| 32 | +if(matrix[start/width][start%width] ==target || |
| 33 | +matrix[end/width][end%width] ==target)returntrue; |
| 34 | +returnfalse; |
| 35 | + } |
| 36 | + |
| 37 | + |
| 38 | +} |