2010/10/21 Brody Berg <[email protected]>:
> (defn binary-search
> "Search sorted list for target using binary search technique"
Binary search is only useful on indexed data types like Clojure Vectors.
> ([m_list target]
> (if (empty? m_list)
> false
> (binary-search m_list 0 (- (count m_list) 1) target))
> )
> ([m_list m_left m_right target]
Because Vectors are persistent you can create Sub-Vectors instead of
keeping tracking offsets.
> (let [gap (- m_right m_left)]
> (if (>= 0 gap)
> (if (== (nth m_list m_left) target)
> (nth m_list m_left)
> false
No need for explicit false.
Using case/compare you can also replace multiple tests by a single
comparison and constant time lookup:
(defn binary-search [v x]
(if (seq v)
(let [half (quot (count v) 2)
middle (v half)]
(case (compare middle x)
-1 (recur (subvec v (inc half)) x)
1 (recur (subvec v 0 half) x)
true))))
Jürgen
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
