function idx = knnsearch ( xd, xi )

%*****************************************************************************80
%
%% knnsearch() indexes the nearest element in a sorted list.
%
%  Discussion:
%
%    knnsearch() is a function in MATLAB's machine learning toolbox which
%    is not available through Octave.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 October 2012
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    real XD(N,1), the sorted data.
%
%    real XI(NI,1), the query values.
%
%  Output:
%
%    integer IDX(NI,1): IDX(I) is the index of the nearest entry in XD to XI(I).
%
  xd = xd(:);
  nd = length ( xd );

  xi = xi(:);
  ni = length ( xi );

  idx = zeros ( ni, 1 );

  for i = 1 : ni

    if ( xi(i) <= xd(1) )

      idx(i) = 1;

    elseif ( xd(nd) <= xi(i) )

      idx(i) = nd;

    else

      l = 1;
      r = nd;

      while ( l + 1 < r )
        m = floor ( ( l + r ) / 2 );
        if ( xi(i) < xd(m) )
          r = m;
        else
          l = m;
        end
      end

      if ( xi(i) - xd(l) < xd(r) - xi(i) )
        idx(i) = l;
      else
        idx(i) = r;
      end

    end

  end

  return
end
