Classical sampling theory is often focused only on the number of samples required to reconstruct a signal. Recent work in adaptive sampling seeks to minimize the number of samples required-- assuming that one can sample at arbitrary locations in the signal. However, in any practical situation, the cost of sampling is not just captured by the number of samples, but also by other possibly time-varying costs of that particular sequence of samples. For example in 2D spatial signals, the sensor has to reposition itself between samples, making the distance between samples relevant in the cost. We show that for one-dimensional threshold classifiers, a tradeoff between number of samples and distance traveled can be achieved using a generalization of binary search, which we refer to as quantile search. We derive an expected rate of convergence and total distance for the case where measurements are noiseless, then show how this algorithm can be extended to account for noisy measurements. We also derive a bound on the expected rate of convergence for the noisy case. Our motivating application is that of studying regions of low oxygen concentration in the Great Lakes. Simulated results are shown for actual lakes of interest, and the methods developed have been implemented on the Platypus Lutra autonomous watercraft for experimental validation on First Sister Lake in Ann Arbor, MI.