Clojure Binary Search

20 Oct

Embarking on “killing two birds with one stone” (play with clojure and brush up on algorithms) adventure, here is my humble implementation of binary search. Without consulting outside sources after about 10 hours in total (my train commute is about an hour each way) the best I could do was:

 1 (defn indexed [coll] (map vector (iterate inc 0) coll))
 2 (defn 
 3   #^{:test (fn [] (tst bin-srch-indx))}
 4   bin-srch-indx [coll el]
 5   (loop [vc-indx (vec (indexed coll))]
 6     (let [sz (count vc-indx), mi (quot sz 2),
 7          ce (get vc-indx mi), [idx v] ce]
 8       (cond
 9         (< el (first coll)) nil
10         (> el (last coll)) nil
11         (and (= mi 0) (or (> el v) (< el v))) nil
12         (= el v) idx
13         (> el v) (recur (subvec vc-indx mi sz))
14         (< el v) (recur (subvec vc-indx 0 mi))))))

indexed on line 1 is an interesting by itself. I came across it in Programming Clojure by Stuart Halloway. It creates new lazy sequence by calling vector with pair of first, then second, etc. items in (iterate (inc 0)) and passed in collection until latter collection is exhausted. bin-srch-indx converts input sequence into a vector, uses cond to catch edge cases and finally uses clojure’s recur and subvec to half the searched collection. On line 3 there is an example of closure to hook in clojure’s build-in test facility. We will talk about test function later.

Unsatisfied with above, I thought there might be a better algorithm for binary search – time to enlist help of Wikipedia. Here is a faster version which doesn’t use subvec but manipulates boundaries.

 1 (defn 
 2   #^{:test (fn [] (tst bin-srch))}
 3   bin-srch [coll el]
 4     (let [v (vec coll)]
 5       (loop [li (int 0), ri (int (count v))]
 6         (if (= (get v 0) el)
 7           0
 8           (let [p (int (/ (- ri li) 2))]
 9             (if
10               (> p 0)
11                 (let [next-p (int (+ li p)),
12                      ce (get v next-p)]
13                   (cond
14                     (= ce el) next-p
15                     (> ce el) (recur li next-p)
16                     (< ce el) (recur next-p ri)))
17               nil))))))

Being a diligent developer, I included test function to prove that code works.

  [f]
    (let 
      [ub1 99999
      ub2 (+ ub1 1)
      tc1 (range 10 ub1 1)
      tc2 (conj tc1 ub2)
      tc3 [11 13 15]
      pli 1
      pui 98
      dc 500
      pcol (take 100 (drop dc primes))]
        (assert (= nil (f tc1 1)))
        (assert (= nil (f tc1 (+ ub2 1))))
        (for [i (range 10 (+ ub1 1) 1)] 
          (assert (= (- i 10) (f tc1 i))))
        (for [i (range 10 (+ ub2 1) 1)] 
          (assert (= (- i 10) (f tc2 i))))
        (assert (= nil (f tc3 14)))
        (assert (= pli
           (f pcol (first (take 1 
              (drop (+ dc pli) primes))))))
        (assert (= pui
           (f pcol (first (take 1 
              (drop (+ dc pui) primes))))))))

Above sets up some test data and using assert verifies results. So, in your friendly REPL you can try:

user=> (use '[clojure.contrib.lazy-seqs :only (primes)])
nil
user=> (test bin-srch)
:ok
user=> (test bin-srch-indx)
:ok
user=> (bin-srch (take 100 primes) 11)
4

Also, here is a complete file bin-srch.clj. Since WordPress upload attachment gods don’t like clj extension, I had to use doc file extension. By the way, I don’t think it would hard to distinguish between text and binary files during upload and allow former. Let’s pray together: Hare WordPress upload attachment gods…:-)

In the next post we will take look how, with a help of clojure macro, we can measure running time of two implementations above.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: