Implementing Binary Search with Clojure

Submitted by viksit on Tue, 04/20/2010 - 01:06

I was trying to implement a simple binary search using a purely functional approach, and after much hacking, googling and wikibooking, came up with this in Clojure.

(defn binarysearch
  ( [lst n]
      (binarysearch lst 0 (dec (count lst)) n))
  ( [lst lb ub n]
      (if (> lb ub) -1 ; this is the case where no element is found
          (let [mid (quot (+ lb ub) 2)
                mth (nth lst mid)]
            (cond
             ; mid > n, so search lower
             (> mth n) (recur lst lb (dec mid) n)
             ; mid < n, search upper
             (< mth n) (recur lst (inc mid) ub n)
             ; else, found, return index
             (= mth n) mid)))))