Findnearest function?


#1

Is there a simple findnearest() function somewhere in Julia-land?

A = [1, 5, 12, 23];
findnearest(A, 14)  
# ->  3
findnearest(A, 18)
# ->  4 

#2

I’ll take a shot at it:

findnearest(A::AbstractArray,t) = findmin(abs(A-t))[2]

Remove the [2] to return nearest value as well. Not sure how to accommodate ties though?


#3

If the array is sorted, like in the post, then the following will return a range with the nearest values:

function findnearest(a,x)
       n = length(a)
       n > 0 || return 0:-1
       i1 = searchsortedlast(a,x)
       i0 = i1
       if i1>0
           while i0>1 && a[i0-1]==a[i0]
               i0 -= 1
           end
           d = x-a[i1]
       else
           i0 = i1+1
           d = a[i1+1]-x
       end
       i2 = i1
       if i2<n && a[i2+1]-x<d
           i0 = i2+1
           d = a[i2+1]-x
           i2 += 1
       end
       while i2<n && a[i2+1]-x==d
           i2 += 1
       end
       return i0:i2
end

Note the details, such as returning a zero-length range when array is empty, and returning a range with values on both sides of x when they are of equal distance.

The OP’s example reproduces as:

julia> A = [1, 5, 12, 23];
julia> findnearest(A, 14)
3:3
julia> # ->  3
       findnearest(A, 18)
4:4
julia> # ->  4

#4

Just to clean things a bit, the last version works, but can take linear time on some inputs (such as a constant long vector).
The following is cleaner and uses just the sorted search functions which are sublinear.

function findnearest(a,x)
       length(a) > 0 || return 0:-1
       r = searchsorted(a,x)
       length(r) > 0 && return r
       last(r) < 1 && return searchsorted(a,a[first(r)])
       first(r) > length(a) && return searchsorted(a,a[last(r)])
       x-a[last(r)] < a[first(r)]-x && return searchsorted(a,a[last(r)])
       x-a[last(r)] > a[first(r)]-x && return searchsorted(a,a[first(r)])
       return first(searchsorted(a,a[last(r)])):last(searchsorted(a,a[first(r)]))
end

Again, we have:

julia> A = [1, 5, 12, 23];
julia> findnearest(A, 14)
3:3
julia> findnearest(A, 18)
4:4

#5

Like @cormullion, I’ve had need for such a function many times, and here is my personal solution for it. Unlike @Dan’s version, this doesn’t care about ties and returns just a single index. Also, as it works on sorted arrays, the function name should be searchsortednearest to be consistent with Julia’s function names (I would expect findnearest to work on any array).

function searchsortednearest(a,x)
   idx = searchsortedfirst(a,x)
   if (idx==1); return idx; end
   if (idx>length(a)); return length(a); end
   if (a[idx]==x); return idx; end
   if (abs(a[idx]-x) < abs(a[idx-1]-x))
      return idx
   else
      return idx-1
   end
end

#6

Neat! By the way, currently Julia 0.6 wants me to:

WARNING: abs{T <: Number}(x::AbstractArray{T}) is deprecated, use abs.(x) instead.

#7

Some good solutions - the simpler offering (@traktofon) benchmarks a bit faster, but both are fine for my needs.

(How about adding a version to Julia, since it appears to be useful? :))


#8

Since it assumes a sorted container, the speed advantage is not surprising.

AFAIK the core developers want to make Julia smaller, and put such functionality in packages. So perhaps you could find a package to submit this to.