- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]Given target =
5
, return true
.Given target =
20
, return false
.
Subscribe to see which companies asked this question
Method 1: slower scanning the lower bound and high bound. easy to understand, cleaner code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public boolean searchMatrix(int[][] matrix, int target) { int x=0,y=matrix.length-1; //binary search y if(target<matrix[0][0])return false; if(matrix.length==1&&matrix[0].length==1) return target==matrix[0][0]; while(x<matrix[0].length && y>=0){ if(target>matrix[y][x]){ x++; } else if(target<matrix[y][x]){ y--; } else{ return true; } } return false; |
Method 2: binary search on both x and y
to be continuued
No comments:
Post a Comment