Significance Adopting the right search strategy is of critical importance in a broad range of natural and man-related activities. For example, when foraging in an environment with scarce resources, the search strategy used by animals to look for nourishment is a matter of life or death. It is generally accepted that, under most conditions, the optimal strategy alternates ballistic and diffusive steps. This, however, does not take into account that many search spaces feature complex topographies with boundaries, barriers, and obstacles. Here, we show that the presence of such complexity shifts the optimal strategy toward less ballistic and more diffusive searches.