advanced code snippet search

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

Expand | Embed | Plain Text 
  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.