Share my JAVA solution using binary search with O(logM + logN)time


  • 1
    S
    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if (row == 0) {
        	return false;
        }
        int col = matrix[0].length;
        int left = 0; 
        int right = row * col - 1;
        int mid = 0;
        if (target > matrix[row - 1][col - 1] || target < matrix[0][0]) {
        	return false;
        }
        while (left <= right) {
        	mid = (left + right) / 2;
        	if (matrix[mid/col][mid%col] == target) {
        		return true;
        	} else if (matrix[mid/col][mid%col] < target) {
        		left = mid + 1;
        	} else {
        		right = mid - 1;
        	}
        }
        return false;
    }

Log in to reply
 

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