A theoretical and applied literature has suggested that foragers search using Lévy flights, since Lévy flights can maximize the efficiency of search in the absence of information on the location of randomly distributed prey. Foragers, however, often have available to them at least some information about the distribution of prey, gained either through evolved mechanisms, experience and memory, or social transmission of information. As such, we might expect selection for heuristics that make use of such information to further improve the efficiency of random search. Here we present a general model of random search behavior that includes as special cases: area-restricted search, correlated random walks, Brownian search, and Lévy flights. This generative model allows foragers to adjust search parameters based on encounter-conditional and other heuristics. Using a simulation model, we demonstrate the efficiency gains of these search heuristics, and illustrate the resulting differences in the distributions of step-size and heading angle change they imply, relative to Lévy flights. We conclude by presenting a statistical model that can be fit to empirical data and a set of testable, quantitative predictions that contrast our model of adaptive search with the Lévy flight foraging hypothesis.