We investigated the relationships between search efficiency, movement strategy, and non-local communication in the biological context of animal foraging. We considered situations where the members of a population of foragers perform either Gaussian jumps or Lévy flights, and show that the search time is minimized when communication among individuals occurs at intermediate ranges, independently of the type of movement. Additionally, while Brownian strategies are more strongly influenced by the communication mechanism, Lévy flights still result in shorter overall search durations.