Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.Arrays;
public class Search2DMatrix{
public boolean searchMatrixOne(int[][] matrix, int target){
int numOfRows = matrix.length;
int numOfColumns = matrix[0].length;
if (numOfRows == 0 || numOfColumns == 0) return false;
// here we assume that the total number of elements in the matrix
// is inside the range of Integer in Java
int total = numOfRows * numOfColumns;
// then we treat the matrix as a large one-dimensional array and do a binary search
int low = 0;
int high = total - 1;
while (low <= high){
int mid = (low + high) / 2;
// now locate the element in the matrix indicated by mid
// better to draw a picture of a simple matrix
int numAtMid = matrix[mid/numOfColumns][(mid%numOfColumns)];
if (target == numAtMid) return true;
if (target > numAtMid){
low = mid + 1;
}else{
high = mid - 1;
}
}
return false;
}
public boolean searchMatrixTwo(int[][] matrix, int target){
// in case m*n is greater than the limit of Java Integer
int numOfRows = matrix.length;
int numOfColumns = matrix[0].length;
if (numOfRows == 0 || numOfColumns == 0) return false;
// use the first pass to get the possible row that the target could reside
int low = 0;
int high = numOfRows - 1;
int rowInd = -1;
while(low < high){
int mid = (low + high) / 2;
if (target >= matrix[mid][0] && target < matrix[mid+1][0]){
rowInd = mid;
break;
}else if(target < matrix[mid][0]){
high = mid - 1;
}else if(target >= matrix[mid+1][0]){
low = mid + 1;
}
}
if (low == high) rowInd = low;
if (high < 0) return false; // this is a tricky boundary case matrix: [[1]] and target: 0
return Arrays.binarySearch(matrix[mid], target) >= 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment