在的Clojure [脚本] ，如何编写一个函数最近接收两个排序载体 A ， B 并返回 A 的 B ？

作为一个例子，

 （最近的[1 2 3 101 102 103] [0 100 1000]）; [0 0 0 100 100 100]
 

我想的解决方案既地道，并有良好的表现：为O（n ^ 2）是不能接受的。

您的帮助是AP preciated ....

使用二进制搜索或排序集即被一O（N * M）的时间复杂度，其中n为（算） 和M （计数B）。

然而利用的事实是a和b的排序的时间复杂度可为O（最大（N，M））

 （defn最近的[A，B]
  （IF-让[更多-B（下一页B）]
    （让[x和y] b
          M（/（+ X×Y）2）
          并[d =米＆GT;米]（分带＃（小于=％米））]
      （懒的猫（重复（COUNT＆LT; = M）X）
        （最近的＆GT;米更多-B）））
    （重复（算）（第一个B））））


=＆GT; （最接近[1 2 3 101 102 103 501 601] [0 100 1000]）
（0 0 0 100 100 100 100 1000）
 

In clojure[script], how to write a function nearest that receives two sorted vectors a, b and returns for each element of a the nearest element of b?

As an example,

(nearest [1 2 3 101 102 103] [0 100 1000]); [0 0 0 100 100 100]

I would like the solution to be both idiomatic and with good performances: O(n^2) is not acceptable!

Your help is appreciated....

Using a binary search or a sorted-set incurs a O(n*log m) time complexity where n is (count a) and m (count b).

However leveraging the fact that a and b are sorted the time complexity can be O(max(n, m)).

(defn nearest [a b]
  (if-let [more-b (next b)]
    (let [[x y] b
          m (/ (+ x y) 2)
          [<=m >m] (split-with #(<= % m) a)]
      (lazy-cat (repeat (count <=m) x)
        (nearest >m more-b)))
    (repeat (count a) (first b))))


=> (nearest [1 2 3 101 102 103 501 601] [0 100 1000])
(0 0 0 100 100 100 100 1000)