chickadee » binary-search » binary-search

Performs a binary search in SEQUENCE, which should be a sorted list or vector. PROC is called to compare items in the sequence, should accept a single argument and return an exact integer: zero if the searched value is equal to the current item, negative if the searched value is less than the current item, and positive otherwise. Returns the index of the found value or #f otherwise.

SEQUENCE may also be an exact integer - in this case the search is performed on an /abstract/ sequence and PROC is called with the current index into the abstract sequence. This may be useful if you just want to iterate over the O(log n) steps needed to locate a value in some particular range.