Unlike laboratory experiments, real-world visual search can contain multiple targets. Searching for an unknown number of targets creates a unique set of challenges for the observer, and often produces serious errors. We propose a Bayesian optimal foraging model to predict and describe behavior in such search scenarios, and investigate whether people adapt their search strategies based on complex statistics of target distributions. Separate groups searched arrays drawn from three target distributions with the same average number of targets per display, but different target-clustering properties. As predicted, participants searched longer when they expected more targets to remain and adjusted their expectations as searches unfolded, indicating that searchers are sensitive to the target distribution, consistent with both an optimal foraging framework and an ideal Bayesian observer. However, compared to the ideal observers, searchers systematically under-adjusted to the target distribution, suggesting that training could improve multiple-target search in radiology and other crucial applications.