Please let me know how to improve it.


  • 0
    Y
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
    	int m = matrix.size();
    	int n = matrix[0].size();
    
    	if (m == 0 || n == 0)
    		return false;
    
    	int row_num; // 1 base
    
    	// search in matrix[i][0] to get row number
    	int low = 1;
    	int high = m;
    	
    	while (low <= high)
    	{			
    		int mid = (low + high) / 2;
    		if (target > matrix[mid-1][0])
    		{
    			low = mid + 1;
    		}
    		else if (target < matrix[mid-1][0])
    		{
    			high = mid - 1;
    		}
    		else
    		{
    			return true;
    		}
    	}
    
    	if (high < low)
    	{
    		if (high == 0)
    		{
    			return false;
    		}
    
    		if (low == m+1)
    		{
    			if (target > matrix[high-1][n-1])
    				return false;
    		}
    
    		row_num = high;
    	}
    
    	// search in row_num row
    	low = 1;
    	high = n;
    
    	while (low <= high)
    	{
    		int mid = (low + high) / 2;
    
    		if (matrix[row_num-1][mid-1] == target) {
    			return true;
    		}
    		else if (matrix[row_num-1][mid-1] < target) {
    			low = mid + 1;
    		}
    		else {
    			high = mid - 1;
    		}
    	}
    
    	return false;
    }
    

    };


Log in to reply
 

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