The searching trajectories of different animals can be described with a broad class of flight length ( l j ) distributions with P ( l j ) = l j –μ . Theoretical studies have shown that changes in these distributions (i.e., different μ values) are key to optimizing the long-term encounter statistics under certain searcher–resource scenarios. In particular, they predict the advantage of Lévy searching (μ ≈ 2) over Brownian motion (μ ≥ 3) for low-prey-density scenarios. Here, we present experimental evidence of predicted optimal changes in the flight-time distribution of a predator's walk in response to gradual density changes of its moving prey. Flight times of the dinoflagellate Oxyrrhis marina switched from an exponential to an inverse square power-law distribution when the prey ( Rhodomonas sp.) decreased in abundance. Concomitantly, amplitude and frequency of the short-term helical path increased. The specific biological mechanisms involved in these searching behavioral changes are discussed. We suggest that, in a three-dimensional environment, a stronger helical component combined with a Lévy walk searching strategy enhances predator's encounter rates. Our results support the idea of universality of the statistical laws in optimal searching processes despite variations in the biological details of the organisms.