两次二分法查找
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 // IMPORTANT: Please reset any member data you declared, as 4 // the same Solution instance will be reused for each test case. 5 int line = searchLine(matrix,0,matrix.length,target); 6 if(line < 0) 7 return false; 8 int result = search(matrix[line],0,matrix[line].length,target); 9 if(result < 0) 10 return false; 11 return true; 12 } 13 public int searchLine(int[][] matrix, int start, int end, int target) 14 { 15 if(start == end-1){ 16 if(matrix[start][0] <= target) 17 return start; 18 else 19 return -1; 20 } 21 int tmp = (start + end)/2; 22 if(matrix[tmp][0] <= target) 23 return searchLine(matrix,tmp,end,target); 24 else 25 return searchLine(matrix,start,tmp,target); 26 } 27 public int search(int[] matrix, int start,int end,int target) 28 { 29 if(start == end-1){ 30 if(matrix[start] != target) 31 return -1; 32 else 33 return start; 34 } 35 int tmp = (start + end)/2; 36 if(matrix[tmp] == target) 37 return tmp; 38 else if(matrix[tmp] < target) 39 return search(matrix,tmp,end,target); 40 else 41 return search(matrix,start,tmp,target); 42 43 } 44 }
注意边界