Java O(log(n)+log(m))


  • 0
    public boolean searchMatrix(int[][] matrix, int target) {
    
        int m = matrix.length, n = matrix[0].length;
    
        int l1 = 0, r1 = m - 1;
        int mid;
    
        while (l1 <= r1) {
    
            mid = (l1 + r1) / 2;
            if (matrix[mid][0] == target) {
                return true;
            }
            if (matrix[mid][0] > target) {
                r1 = mid - 1;
            }
            if (matrix[mid][0] < target) {
                l1 = mid + 1;
            }
        }
    
        if (l1 == 0) {
            return false;
        }
    
        int l2 = 0, r2 = n - 1;
        int mid2;
    
        while (l2 <= r2) {
    
            mid2 = (l2 + r2) / 2;
    
            if (matrix[r1][mid2] == target) {
                return true;
            } else if (matrix[r1][mid2] > target) {
                r2 = mid2 - 1;
            } else {
                l2 = mid2 + 1;
            }
    
        }
    
        return false;
    
    }

Log in to reply
 

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