Many foraging animals find food using composite random search strategies, which consist of intensive and extensive search modes. Models of composite search can generate predictions about how optimal foragers should behave in each search mode, and how they should determine when to switch between search modes. Most of these models assume that foragers use resource encounters to decide when to switch between search modes. Empirical observations indicate that a variety of organisms use non-directional sensory cues to identify areas that warrant intensive search. These cues are not precise enough to allow a forager to directly orient itself to a resource, but can be used as a criterion to determine the appropriate search mode. As a potential example, a forager might use olfactory information as a non-directional cue. Even if scent is too imprecise for the forager to immediately locate a specific food item, it might inform the forager that the area is worth searching carefully. We developed a model of composite search based on non-directional sensory cues. With simulations, we compared the search efficiencies of composite foragers that use resource encounters as their mode-switching criterion with those that use non-directional sensory cues. We identified optimal search patterns and mode-switching criteria on a variety of resource distributions, characterized by different levels of resource aggregation and density. On all resource distributions, foraging strategies based on the non-directional sensory criterion were more efficient than those based on the resource encounter criterion. Strategies based on the non-directional sensory criterion were also more robust to changes in resource distribution. Our results suggest that current assumptions about the role of resource encounters in models of optimal composite search should be re-examined. The search strategies predicted by our model can help bridge the gap between random search theory and traditional patch-use foraging theory.