Skip to content

Instantly share code, notes, and snippets.

@theronic

theronic/binary_search.clj

Last active June 18, 2020 10:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save theronic/2fffdbeb0decbdf86625d7202676f1a3 to your computer and use it in GitHub Desktop.
Save theronic/2fffdbeb0decbdf86625d7202676f1a3 to your computer and use it in GitHub Desktop.
Download ZIP
Binary Search in Clojure
Raw
binary_search.clj
(defn binary-search
"Finds a value in a sorted seq in log(N) time."
[coll target]
(if (seq coll)
(let [half (int (/ (count coll) 2))
pivot (nth coll half nil)]
(if (= pivot target)
pivot
(if (< target pivot)
(binary-search (take half coll) target)
(binary-search (drop (inc half) coll) target))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment