Solution with O(logM + logN)


  • 1
    N
    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
                    int m = matrix.size();
    	int n = matrix[0].size();
    
    	//binary search rows
    	int low = 0, mid=0, row = -1;
    	int high = m - 1;
    	while(low <= high)
    	{
    		mid = (high+low)/2;
    		if (matrix[mid][0] <= target)
    		{
    			if(matrix[mid][n-1]>= target)	//find the row
    			{	
    				row = mid;
    				break;
    			}
    			else
    				low = mid+1;
    		}
    		else
    			high = mid - 1;
    	}
    
    	if(row == -1)
    		return false;
    	//binary search column value
    	low = 0; high = n-1;
    	while (low<=high)
    	{
    		mid = (high + low)/2;
    		if (matrix[row][mid] == target)
    			return true;
    		else if (matrix[row][mid] < target)
    			low = mid+1;
    		else
    			high = mid-1;
    	}
    	return false;
        }
    };

  • 1
    L
    // C++11 lambda and auto test
    class Solution
    {
    public:
    	bool searchMatrix(vector<vector<int> > &matrix, int target)
    	{
    		auto it = upper_bound(matrix.begin(), matrix.end(), target, 
    			[](int x, const vector<int> &a) { return x < a[0];});
    		if (it == matrix.begin()) return false;
    		it--;
    		auto jt = equal_range(it->begin(), it->end(), target);
    		if (jt.first == jt.second) return false;
    		else return true;
    	}
    };

  • 0
    T

    I think this method is tuned to be wrong, for you can't decide which row may the value would be. For example, the [1, 3, 5, 13][10, 11, 16, 20][23, 30, 34, 50] and try to find target 13, this algorithm tune to get the answer.


  • 0
    J

    @tornador92 The first integer of each row is greater than the last integer of the previous row.


Log in to reply
 

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