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.