Search 2D matrix obvious solution


  • 0
    P
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            bool found;
    
    	    // First step consists of determining the range
        	for(int r = 0; r < matrix.size(); r++)
        	{
        		if(matrix[r][0] > target)
        			return false;
        		else if(matrix[r][0] == target)
        			return true;
        		else
        		{
        			found = dichotomicSearch(matrix[r], target);
        			if(found) return true;
        		}
        	}
        	
        	return false;
        }
        
        bool dichotomicSearch(vector<int>& rows, int target)
        {
        	int m;
        	int start = 0;
        	int end = rows.size();
        
        	while(end - start > 1)
        	{
        		m = (end + start) / 2;
        
        		if(rows[m] == target) return true;
        		else if(rows[m] > target) end = m;
        		else start = m;
        	}
        
        	if(rows[start] == target) return true;
        	else return false;
        }
    };

Log in to reply
 

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