  This paper considers a target localization problem where at any given time an
agent can choose a region to query for the presence of the target in that
region. The measurement noise is assumed to be increasing with the size of the
query region the agent chooses. Motivated by practical applications such as
initial beam alignment in array processing, heavy hitter detection in
networking, and visual search in robotics, we consider practically important
complexity constraints/metrics: \textit{time complexity}, \textit{computational
and memory complexity}, and the complexity of possible query sets in terms of
geometry and cardinality.
  Two novel search strategy, $dyaPM$ and $hiePM$, are proposed. Pertinent to
the practicality of out solutions, $dyaPM$ and $hiePM$ are of a connected query
geometry (i.e. query set is always a connected set) implemented with low
computational and memory complexity. Additionally, $hiePM$ has a hierarchical
structure and, hence, a further reduction in the cardinality of possible query
sets, making $hiePM$ practically suitable for applications such as beamforming
in array processing where memory limitations favors a smaller codebook size.
  Through a unified analysis with Extrinsic Jensen Shannon (EJS) Divergence,
$dyaPM$ is shown to be asymptotically optimal in search time complexity
(asymptotic in both resolution (rate) and error (reliability)). On the other
hand, $hiePM$ is shown to be near-optimal in rate. In addition, both $hiePM$
and $dyaPM$ are shown to outperform prior work in the non-asymptotic regime.
