Understanding the structural complexity and the main drivers of animal search behaviour is pivotal to foraging ecology. Yet, the role of uncertainty as a generative mechanism of movement patterns is poorly understood. Novel insights from search theory suggest that organisms should collect and assess new information from the environment by producing complex exploratory strategies. Based on an extension of the first passage time theory, and using simple equations and simulations, we unveil the elementary heuristics behind search behaviour. In particular, we show that normal diffusion is not enough for determining optimal exploratory behaviour but anomalous diffusion is required. Searching organisms go through two critical sequential phases (approach and detection) and experience fundamental search tradeoffs that may limit their encounter rates. Using experimental data, we show that biological search includes elements not fully considered in contemporary physical search theory. In particular, the need to consider search movement as a non-stationary process that brings the organism from one informational state to another. For example, the transition from remaining in an area to departing from it may occur through an exploratory state where cognitive search is challenged. Therefore, a more comprehensive view of foraging ecology requires including current perspectives about movement under uncertainty.