Posted By

bigfaceworm on 04/19/10


Tagged

search binary


Versions (?)

Binary Search


 / Published in: Emacs Lisp
 

In response to this challenge: http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent

  1. (defun bsearch (vec elt)
  2. "binary search VEC for ELT, returning index, or -1 if not found"
  3. (bsearch-impl vec elt 0 (- (length vec) 1)))
  4. (defun bsearch-impl (vec target left right)
  5. (let ((mid (/ (+ left right) 2)))
  6. (cond ((eq left right)
  7. (if (eq target (elt vec left))
  8. left
  9. -1))
  10. ((<= target (elt vec mid))
  11. (bsearch-impl vec target left mid))
  12. (t ; target > (elt vec mid)
  13. (bsearch-impl vec target (+ 1 mid) right)))))

Report this snippet  

You need to login to post a comment.