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


  • 0
    S

    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;
        }
    }

Log in to reply
 

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