# 3 Java solutions: 2-binarySearch, 1-binarySearch-recursive and 1-binarySearch-iterative

• 2-binarySearch

``````public class Solution1 {
// Two binary search: search target row, then search target value
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
// target row
int[] first = new int[m];
for (int i = 0; i < m; i++) first[i] = matrix[i][0];
int row = Arrays.binarySearch(first, target);
if (row >= 0) return true;
row = -(row + 1) - 1;
// target value
if (row < 0) return false;
return Arrays.binarySearch(matrix[row], target) >= 0;
}
}
``````

1-binarySearch-recursive

``````public class Solution2 {
// One binary search: treat f[i] as matrix[i / n][i % n]
// Recursive
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
return binarySearch(matrix, n, target, 0, m * n - 1);
}

private boolean binarySearch(int[][] matrix, int n, int target, int lo, int hi){
if (lo > hi) return false;
int mid = lo + (hi - lo) / 2;
int cmp = matrix[mid / n][mid % n] - target;
if (cmp == 0) return true;
else if (cmp > 0)
return binarySearch(matrix, n, target, lo, mid - 1);
else
return binarySearch(matrix, n, target, mid + 1, hi);
}
}
``````

1-binarySearch-iterative

``````public class Solution3 {
// One binary search: treat f[i] as matrix[i / n][i % n]
// Iterative
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int lo = 0, hi = m * n - 1;
while (lo < hi){
int mid = lo + (hi - lo) / 2;
int cmp = matrix[mid / n][mid % n] - target;
if (cmp == 0) return true;
else if (cmp > 0) hi = mid - 1;
else              lo = mid + 1;
}
return matrix[lo / n][lo % n] == target;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.