Madness is triggered so you do not have to pay the other costs till it comes off the stack. It will not go on the stack until after Frantic Search is done resolving.
From Rules:
702.32a Madness is a keyword that represents two abilities. The first is a static ability that functions while the card with madness is in a player's hand. The second is a triggered ability that functions when the first ability is applied. "Madness [cost]" means "If a player would discard this card, that player discards it, but may exile it instead of putting it into his or her graveyard" and "When this card is exiled this way, its owner may cast it by paying [cost] rather than paying its mana cost. If that player doesn't, he or she puts this card into his or her graveyard."
702.32b Casting a spell using its madness ability follows the rules for paying alternative costs in rules 601.2b and 601.2e-g.
