Skip to content

Instantly share code, notes, and snippets.

@sergiobuj
Created August 31, 2016 17:44
Show Gist options
  • Save sergiobuj/1035594af6c93d874fd3da31d6cb1f64 to your computer and use it in GitHub Desktop.
Save sergiobuj/1035594af6c93d874fd3da31d6cb1f64 to your computer and use it in GitHub Desktop.
Learning CLisp - Implement Binary Search
(defun binary-search (key collection) ;; Function with simple signature
(defun binary-search-recursion (data element lower upper) ;; Helper function with multiple parameters
(let* ((range (- upper lower))
(mid (+ lower (round (/ range 2))))
(value (nth mid data)))
(cond
((= value element) mid)
((< range 1) -1)
((< value element) (binary-search-recursion data element (+ mid 1) upper))
((> value element) (binary-search-recursion data element lower (- mid 1))))))
(binary-search-recursion collection key 0 (- (length collection) 1))) ;; Call the helper function and recurse
(let* ((data '(10 20 30 40 50 60 70 80 90 99))
(value 20)
(index (binary-search value data)))
(format t "~d" index))
@lispm
Copy link

lispm commented Sep 4, 2016

DEFUN should not be nested. Use FLET or LABELS for local functions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment