Recent attempts to integrate function and mechanism have resulted in an appreciation of the relevance of forager psychology to understanding the functional aspects of foraging behaviour. Conversely, an acknowledgement of the functional diversity of learning mechanisms has led to greater understanding of the adaptive nature of cognition. In this paper, we present data from three experiments suggesting that noisy miner birds use different cognitive strategies when searching for foods with different distributions. When searching for nectar, an immobile, readily depleted resource, birds spontaneously attend to fine-scale spatial information and use a spatial memory-based strategy that is efficient in a novel context and largely resistant to disruptions to movement. When searching for invertebrates, a mobile, clumped and cryptic resource, birds employ a strategy whose efficiency increases with increased task familiarity, is vulnerable to disruptions to their movement and may rely more on memory for movement rules than memory for location information. Previous reports of adapted cognition have reported performance differences between species (for example, better spatial cognitive performance in storing versus non-storing birds). Ours is the first study to demonstrate that differences in cognitive strategy (as opposed to just enhanced performance) occur within a single species in different foraging contexts. As well as providing an example of how specially adapted cognitive mechanisms might work, our data further emphasise the importance of jointly considering functional and mechanistic aspects to fully understand the adaptive complexities of behaviour.