In this paper, we propose efficient information search methods based on the user utility in super-distributed environments, where the released information can be renewed or deleted freely by administrators of independent information sites. In an efficient search, a user (or a searcher) can find the desired information with high satisfaction, i.e., user utility. Generally, the greater the search time and cost required in order to increase target discovery probability, the lower the user utility becomes. Here, we propose efficient methods for conducting searches for multiple targets. Especially, keeping in mind that utility decreases monotonically with time or cost, we give high priority to the search of the target information the utility of which decreases sharply. And finally, we show the effectiveness of the proposed methods by computer simulations.