CLEAR O(lgm + lgn) JAVA Solution based on Binary Search


  • 2

    Key point:

    Imagine a one-dimension sorted array composed of row by row of the matrix.

    Runtime = O(lg(mn)) = O(lgm + lgn)*

    JAVA Code:

    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length, start = 0, end = m * n  - 1;
        while (start < end) {
        	int mid = (start + end) / 2;
        	if (matrix[mid/m][mid%m] == target) return true;
        	else if (matrix[mid/m][mid%m] > target) end = mid;
        	else start = mid + 1;
        }        
        return (matrix[start/m][start%m] == target);
    }

  • 1
    I

    Why if hte middle element > target you set end to mid not end = mid - 1 like in normal binary search?


Log in to reply
 

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