Binary search algorithm in Clojure

Question

I'm absolutely new to Clojure (started learning it yesterday). After I went through some tutorials and checked out the basics I implemented the following Binary search algorithm:

(defn log-search
 [elements, elem-to-find]
 (loop [left 0
 right (- (count elements) 1)]
 (when (<= left right)
 (def m (int (Math/floor (/ (+ left right) 2))))
 (def actual (nth elements m))
 (cond
 (= actual elem-to-find) m
 (< actual elem-to-find) (recur (+ m 1) right)
 (> actual elem-to-find) (recur left (- m 1))))))

The followings are intentional in the implementation:

1. returning nil on empty sequence
2. I return nil if the element is not present
3. I do not care if (+ left right) overflows on very big sequence (I'm focusing only on the language features)

My questions:

1. Is there any Clojure (or funcional programming) antipattern in the code?
2. What would be a more functional (or Clojure) approach?

Any other suggestions are more than welcomed.

Thank you.

Answer 1

Your implementation is pretty similar to this one: https://programming-pages.com/2012/01/31/binary-search-in-clojure/

I think the overall algorithm is OK. You should avoid using def inside function - that should be used only for global top-level vars -> use let instead. Also, the code formatting is incorrect - use 2 spaces and proper indentation:

(defn log-search
 [elements elem-to-find]
 (loop [left 0
 right (dec (count elements))]
 (when (<= left right)
 (let [m (int (Math/floor (/ (+ left right) 2)))
 actual (nth elements m)]
 (cond
 (= actual elem-to-find) m
 (< actual elem-to-find) (recur (+ m 1) right)
 (> actual elem-to-find) (recur left (- m 1)))))))

Answer 2

Please use let rather than def inside your defn. loop-recur, reduce and iterate can be substituted for each other. iterate is lazy and uses a state->state function that is easy to reason about as you are only looking at the essential thing being done. The tricky part of iterate is that it returns an infinite sequence, so you need to know how to stop it. I would recommend starting off with say (take 3), just to see what is going on.

Answer 3

We can simplify Juraj Martinka's solution in several ways:

• Assume that elements is a vector. You can make it one using vec
  if need be. This gives us constant time lookup, whereas nth is linear in the size of elements.
• Replace (int (Math/floor (/ (+ left right) 2))) with (quot (+ left right) 2).
• Drop the final cond condition: if reached, it is always true. The idiom is to use :else as the true value.
• Use inc and dec where appropriate.

The only significant change is the first.

This gives us

(defn log-search
 [elements, elem-to-find]
 (loop [left 0
 right (dec (count elements))]
 (when (<= left right)
 (let [m (quot (+ left right) 2)
 actual (elements m)]
 (cond
 (= actual elem-to-find) m
 (< actual elem-to-find) (recur (inc m) right)
 :else (recur left (dec m)))))))

For example,

(def stuff [3 5 6])
(map (partial log-search stuff) (range 10))
=> (nil nil nil 0 nil 1 2 nil nil nil)