Research on information search has found widespread evidence of a “positive test strategy” (PTS), where people search for predicted outcomes of a focal hypothesis. A recent analysis by Navarro and Perfors (2011) showed that the PTS is consistent with normative models of search under “sparse” hypothesis spaces, where each possible outcome is predicted by a minority of hypotheses (a property shared by common kinds of categories). Despite this justification, learning often involves a transition to a “dense” hypothesis space as information is accumulated, at which point the PTS becomes markedly worse than a strategy of searching for diagnostic information about multiple hypotheses. Using a perceptual search task, our experiment tested whether people independently switch between these strategies based solely on changes in sparsity. The results show that, in general, people continue to make errors consistent with the PTS even when faced with “dense” hypothesis spaces where that strategy is ineffective.