Please tell me why my solution of binary search twice cost 15-16ms.


  • 0
    E

    class Solution
    {
    public:

    bool searchMatrix(vector<vector<int>> & matrix, int target)
    {
    	if (matrix.size() <= 0)
    	{
    		return false;
    	}
    	
    	if (matrix[0].size() <= 0)
    	{
    		return false;
    	}
    	
    	int iStartIndex = 0;
    	int iEndIndex   = matrix.size() - 1;
    	
    	while (iStartIndex <= iEndIndex)
    	{
    		int iMidIndex = iStartIndex + (iEndIndex - iStartIndex) / 2;
    		
    		if (target == matrix[iMidIndex][0])
    		{
    			return true;
    		}
    		
    		if (target < matrix[iMidIndex][0])
    		{
    			iEndIndex = iMidIndex - 1;
    		}
    		
    		if (target > matrix[iMidIndex][0])
    		{
    			iStartIndex = iMidIndex + 1;
    		}
    	}
    	
    	if (iStartIndex <= 0)
    	{
    		return false;
    	}
    	
    	int iDstLineIndex = iStartIndex - 1;
    	iStartIndex       = 0;
    	iEndIndex         = matrix[iDstLineIndex].size() - 1;
    	
    	while (iStartIndex <= iEndIndex)
    	{
    		int iMidIndex = iStartIndex + (iEndIndex - iStartIndex) / 2;
    		
    		if (target == matrix[iDstLineIndex][iMidIndex])
    		{
    			return true;
    		}
    		
    		if (target < matrix[iDstLineIndex][iMidIndex])
    		{
    			iEndIndex = iMidIndex - 1;
    		}
    		
    		if (target > matrix[iDstLineIndex][iMidIndex])
    		{
    			iStartIndex = iMidIndex + 1;
    		}
    	}
    	
    	return false;
    }
    

    };


Log in to reply
 

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