bisect-search.ss
_bisect-search.ss_
Bisection search
This is a partial port of the 'bisect.py' module from Python's
Standard Library. This module provides two functions,
_vector-bisect-left_ and _vector-bisect-right_, to allow one to do a
bisection-search across a sorted list.
Unlike binary search, we return the index where we expected the key
element to live. If the element already exists, then in the case of
vector-bisect-left, we'll return the index to the left, and visa-versa
for the right-hand-size.
For example:
> (require (planet "bisect-search.ss" ("dyoo" "bisect-search.plt" 1 0)))
> (define (numeric-cmp x y)
(cond [(< x y) -1]
[(= x y) 0]
[else 1]))
> (define (grade score)
(define grades "FEDCBA")
(define breakpoints (vector 30 44 66 75 85))
(string-ref
grades
(vector-bisect-right breakpoints numeric-cmp score)))
> (map grade '(33 99 77 44 12 88))
(#\E #\A #\B #\D #\F #\A)
API
---
> (vector-bisect-left vector compare-function key) FUNCTION
Returns the left bisection point of key, assuming that vector is sorted
consistant to the total ordering defined in compare-function.
> (vector-bisect-right vector compare-function key) FUNCTION
Returns the right bisection point of key, assuming that vector is sorted
consistant to the total ordering defined in compare-function.