algorithm - 在clojure [script]中，如何返回2个排序向量之间的最近元素

在clojure[script]中，如何编写一个函数nearest，该函数接收两个排序向量a，b，并返回a中每个元素的最近元素？
举个例子，

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

我希望解决方案既地道又有良好的性能：b是不可接受的！

最佳答案

使用二进制搜索或排序集合导致O（n*log m）时间复杂度，其中n是cc>和m (count a)。
然而，利用A和B被排序的事实，时间复杂度可以是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)