Add optional distance range to function
I think this depends a lot on your motivation for separating these into two methods.

One simple option I would consider first is to just have 1 version of each of these functions to avoid the duplication in the first place. 
The caller can just ignore the max_dist value if they don't need it.

If performance is an issue and max_distcalculation could be a bottleneck, you could add a Boolean argument to the single function to indicate if max_dist should be calculated or not.

If the logic for max_dist is complex enough to hurt the readability of the basic search, I think you may be better off going with the duplication instead of doing something more complex.  It could be done, but not in a way I would consider reasonable in most cases.