We consider the problem of searching for one or more targets in an environment using a noisy multi-scale sensor. This work utilizes the recently introduced probabilistic quadtree (PQ) framework and provides several improvements and extensions. This framework allows searchers to maintain a compact representation of their belief of the world, while allowing them to consider sensing at various scales. Improvements herein include: reduced computational complexity on our previously used objective function, an alternative quadtree updating technique, and a new searcher objective function. In addition to theoretical contributions, this work considers the problem of coordinating multiple searchers using the PQ structure. Several experiments are included which demonstrate the performance of the algorithms under various congurations and conditions.