Share my java O(log(m*n)) solution


  • 0
    M
    public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null)
            return true;
        int low = 0;
        int height = matrix.length - 1;
        int mid = (low + height)/2;
        int rightMid = 0;
        
        while(low <= height) {
            mid = (low + height)/2;
            if(matrix[mid][0] == target)
                return true;
            if(mid == matrix.length - 1)
                break;
            if(matrix[mid][0] < target && matrix[mid + 1][0] > target)
                break;
            if(matrix[mid][0] > target) {
                height = mid - 1;
            }
            else    {
                low = mid + 1;
            }
        }
        if(matrix[rightMid][0] > target)
            return false;
        // get a right mid 
        rightMid = mid;
        low = 0;
        height = matrix[0].length - 1;
        while(low <= height) {
            mid = (low + height)/2;
            if(matrix[rightMid][mid] == target) 
                return true;
            if(matrix[rightMid][mid] > target)
                height = mid - 1;
            else
                low = mid + 1;
        }
        
        return false;
        
    }
    

    }


Log in to reply
 

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