# Java solution O(m+log(n)) with recursive binary search

• worst case is the last row of the matrix contains the target. In the runtime analysis, m refers to the # of rows, n refers to the # of elements in a row. Binary search is O(log(n)).

``````public class Solution {
public boolean binarySearch(int[] nums, int target, int iMin, int iMax) {
int iMid = (iMin + iMax)/2;
int num = nums[iMid];
// base case
if (target == num) { return true; }
if (iMin > iMax) { return false; }

// recursive case
if (target < num) {
return binarySearch(nums, target, iMin, iMid-1);
} else {
return binarySearch(nums, target, iMid+1, iMax);
}
}

public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) { return false; }

for (int i = 0; i < matrix.length; i++) {
int[] row = matrix[i];
int low = row[0];
int high = row[row.length-1];
//if (target == low || target == high) { return true; }
if (target >= low && target <= high) {
return binarySearch(row, target, 0, row.length-1);
}
}
return false;
}
}``````

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