Chemotactic bacteria lack a sense of position and their motion is perturbed by thermal noise, yet guided by the local gradient in nutrient concentration they can find its source. Macroscopic searchers endowed with a sense of direction and position often face a different problem: lack of local clues pointing towards the location of the target. For example, animals sensing odors in air or water detect them only intermittently as patches of odor sweep by, carried by winds and currents. Because of randomness of the advection and mixing process, local gradients of odor intensity do not point to the source and the searcher must devise a strategy of movement based upon sporadic cues and partial information. I shall discuss a search algorithm, ``infotaxis'', designed to work under such conditions, based on the idea that the rate of acquisition of information on source location can play the same role as concentration in chemotaxis. Its efficiency is demonstrated computationally using a model of odor plume propagation as well as experimental data. Infotactic trajectories feature zigzagging and casting paths similar to those observed in flights of moths and birds. The proposed search algorithm is relevant to the design of olfactory robots with applications to detection of chemical leaks and explosives. The general idea of infotaxis can be applied more broadly in the context of searching with sparse information and provides a framework for quantitative understanding of the balance between the competing ``exploration" and ``exploitation" behaviors in learning processes.