4ms Binary Search O(n*log(n))


  • 0
    S

    The quick idea is to use Binary Search for a complement number.
    There is another idea is to use 2 runners until desired sum is found.

    vector<int> twoSum(vector<int>& numbers, int target)
        {
            // predefine result if no items found
            vector<int> res(2, -1);
            
            for (int ndxFirst=0; ndxFirst<(numbers.size()-1); ++ndxFirst)
            {
                // skip same numbers if sum not equal to target
                if (numbers[ndxFirst] == numbers[ndxFirst+1])
                {
                    if ((numbers[ndxFirst] + numbers[ndxFirst+1]) == target)
                    {
                        res[0] = ndxFirst+1;
                        res[1] = ndxFirst+2;
                        break;
                    }
                    else
                    {
                        continue;
                    }
                    
                }
                
                // if first number is bigger than target - you wont find second anyway.
                if (numbers[ndxFirst] > target)
                {
                    break;
                }
                
                // search for complement number starting from ndxFisrt+!
                int ndxSecond = binarySearch(numbers, ndxFirst+1, target-numbers[ndxFirst]);
                
                // if complement number is found - store them into result and finish
                if (ndxSecond != -1)
                {
                    res[0] = ndxFirst+1;
                    res[1] = ndxSecond+1;
                    break;
                }
            }
            
            return res;
        }
        
        int binarySearch(vector<int> &numbers, int ndxStart, int value)
        { 
            int ndxEnd = numbers.size()-1;
            
            while (ndxStart <= ndxEnd)
            {
                int ndxMiddle = (ndxEnd-ndxStart)/2 + ndxStart;
    
                // if middle number is bigger than desired - search in the left partition
                if (value < numbers[ndxMiddle])
                    ndxEnd = ndxMiddle-1;
                
                // if middle number is smaller than desired - search in the right partition
                else if (value > numbers[ndxMiddle])
                    ndxStart = ndxMiddle+1;
                
                // else is when value and middle number are equal, which means we found it.
                else
                    return ndxMiddle;
            }
            
            return -1;
        }
    

  • 0
    L

    your code needs 8ms in my submit


Log in to reply
 

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