Skip to content

Instantly share code, notes, and snippets.

@pyrocat101
Last active December 20, 2015 00:49
Show Gist options
  • Save pyrocat101/6044872 to your computer and use it in GitHub Desktop.
Save pyrocat101/6044872 to your computer and use it in GitHub Desktop.
(defn binary-search [items value]
(letfn
[(do-search
[items offset]
(let [/ (comp long /)
mid (/ (dec (count items)) 2)
mid-value (items mid)]
(cond
;; found
(= value mid-value) (+ offset mid)
;; not found
(= 1 (count items)) -1
;; less than
(< value mid-value)
(let [items (subvec items 0 mid)]
(recur items offset))
;; greater than
(> value mid-value)
(let [items (subvec items (inc mid))
offset (+ offset (inc mid))]
(recur items offset)))))]
(do-search items 0)))
;;; a little test
(let
[xs (->> (range 1000) (filter even?) vec)]
(every? #(= % (* 2 (binary-search xs %)))
xs))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment