Small Fix for Binsearch In ‘ANSI Common Lisp’ by Paul Graham
November 23rd, 2007 by proj
I found a small bug in the binary search described in Paul Graham’s book ‘ANSI Common Lisp’. When I wrote a few unit tests for the code snippet on page 60 I found that there is unbounded recursion when the item exists below the lower bound of the vector being searched. It’s really a small issue, to correct it replace:
(let ((range (- end start)))...
With:
(let ((range (max 0 (- end start))))...
This now correctly terminates the recursion.
I’m near the end of the book now and I have to say that so far it’s the best book I’ve read on CL yet. I’ve read LISP 3rd Edition by Winston and Horn and a good part of Practical Common Lisp. All three books are great but I think for experienced programmers ‘ANSI Common LISP’ has better examples, explanations and is just written better overall.
Incidentally I finally switched over to markdown http://daringfireball.net/projects/markdown/syntax for my blog posts. Which makes including code samples so much easier.
Here’s the full binary search example from the book with my fix:
(defun bin-search (obj vec)
(let ((len (length vec)))
(and (not (zerop len))
(finder obj vec 0 (- len 1)))))
(defun finder (obj vec start end)
(let ((range (max 0 (- end start))))
(if (zerop range)
(if (eql obj (aref vec start))
obj
nil)
(let ((mid (+ start (round (/ range 2)))))
(let ((obj2 (aref vec mid)))
(if (< obj obj2)
(finder obj vec start (- mid 1))
(if (> obj obj2)
(finder obj vec (+ mid 1) end)
obj)))))))
(defun run-tests ()
(let ((vec (vector 1 2 3 4 5 6 7 8 9 10 11)))
(labels ((test (input expect)
(let ((res (bin-search input vec)))
(let ((passed (eql expect res)))
(format t "~A: bin-search for ~A in ~A -> ~A~%" passed input vec res)))))
(test 1 1)
(test 3 3)
(test 7 7)
(test 11 11)
(test 12 nil)
(test 10210976 nil)
(test 0 nil)
(test -1 nil))))
(run-tests)
Related posts: