#74
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
在一個2D matrix中找某integer是否存在。
Concept find out target belongs to which row, then use binary search 看每個row的最後一個element,若比target大,則target可能在該row。
Implementation 找到row後,要在那個row裡binary search, 此時有出一點小問題: 一開始我將l和r都設成mid,r 發現當target不存在row中時,會無法跑出迴圈, l和r會是相鄰的兩個element。 最後改成l = mid+1, r = mid-2就好了。
Code
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
/*
find out target belongs to which row, then use binary search
*/
int m = matrix.length;
if(m==0) return false;
int n = matrix[0].length;
if(n==0) return false;
int row = 0;
if(matrix[m-1][n-1] < target)
return false;
while(matrix[row][n-1] < target && row < m){
row++;
}
int l=0, r=n;
while(l <= r){
int mid = (l+r)/2;
//if((r-l)==1 && target > matrix[row][l] && target < matrix[row][r])
// break;
if(matrix[row][mid] < target){
l = mid+1;
}else if(matrix[row][mid] > target){
r = mid-1;
}else{
return true;
}
}
/*for(int i=0; i<n; i++){
if(target == matrix[row][i])
return true;
}*/
return false;
}
}