Binary search on an ordered matrix


  • 47
    L
    /**
     *  Do binary search in this "ordered" matrix
     */
    public boolean searchMatrix(int[][] matrix, int target) {
    	
    	int row_num = matrix.length;
    	int col_num = matrix[0].length;
    	
    	int begin = 0, end = row_num * col_num - 1;
    	
    	while(begin <= end){
    		int mid = (begin + end) / 2;
    		int mid_value = matrix[mid/col_num][mid%col_num];
    		
    		if( mid_value == target){
    			return true;
    		
    		}else if(mid_value < target){
    			//Should move a bit further, otherwise dead loop.
    			begin = mid+1;
    		}else{
    			end = mid-1;
    		}
    	}
    	
    	return false;
    }

  • 0
    C

    Same idea. Consider the matrix as a sorted array and apply the normal binary search.


  • 0
    T

    int mid = (begin + end) / 2;

    should be

    int mid = begin + (begin + end) / 2;


  • 2
    D

    should be
    int mid = begin + (end - begin) / 2


  • 0
    T

    yeah, my mistake


  • 0
    Z

    I wonder what's the difference between these two expressions.


  • 6
    F

    Hi, ztyhlzr. The tricky difference between (begin + end) / 2 and begin + (end - begin) / 2 is that there may be overflow for the former if both begin and end are large but won't be a problem for the latter.


  • 0
    D

    I thought the same, but wouldn't it be faster to first skip all the rows whose last element is smaller than the target?

    Semi pseudo:

    for (int i = 0; i < numOfRows; i++)
        {
            if (matrix[i, numOfColumns - 1] < x)
                continue;
            else
               return binarySearch(remainderOfMatrix);
        }
    

    , or would the binary over the entire matrix as an array still be faster on its own?


  • 0
    D

    I like when people downvote without explaining why. Sorry for asking a question i guess.


  • 0
    This post is deleted!

  • 9

    Why you might want to consider some other solution instead of this -

    1. row_num * col_num might cause overflow.

    2. Also,/ and % are expensive operations.

    3. For more problems with this solution, Refer to the comments in this solution : https://leetcode.com/discuss/10735/

    Great solution, but
    I think there are better solutions than just treating it as a list.


  • 0
    A

    By looking for a suitable row first and then doing a binary search, you end up with a runtime complexity of O( rows + log( cols ) ); whereas, if you treat the whole search space as a single array, you end up with a runtime complexity of O( log( rows * cols ) ). So, to put it in context, imagine you have a 2-dimensional array consisting of 1-million rows and 10-columns, then you'll end up with the following:

    1000000 + log( 10 ) = 1000001

    log( 1000000 * 10 ) = 7

    Your approach will have 1000001 operations, whereas the latter will have only 7.


  • 0
    D

    @aroux to look for a suitable row, you can also use binary search, which takes O(log row). These 2 methods have the same running time. But treating 2d array as a 1d array may cause overflow.


  • -1
    D

    Will not work for input
    [[1,2,3,4,5],[3,4,6,11,14],[5,7,9,12,15],[7,9,15,20,22],[9,12,16,25,29]]
    11


  • 0
    J

    @dipenthakkar Your input is invalid.


  • 2
    J

    Could someone explain what is happening when he does division for the row value and modulus for the column value?


  • 1
    G

    Cannot pass the test, you missed one line:

    if (matrix.length == 0 || matrix[0].length == 0) return false;
    

  • 0
    A
     bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.size()==0)
                return false;
            int m=matrix.size(); int n=matrix[0].size();
            int row=0,column=n-1; 
            while(row<m && column>=0)
            {
                if(matrix[row][column]==target)
                    return true;
                else if(matrix[row][column] >target)
                    column--;
                else
                    row++;
            }
            return false;
        }
     Simple Solution Accepted in one Go

Log in to reply
 

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