Binary Search🔗ℹ

This module provides functions for performing binary search where the search space is indexed by exact integers.

procedure
(binary-search data
goal
[ start
end
#:compare compare
#:mode mode]) → (or/c exact-integer? #f)
  data : (or/c (-> exact-integer? any/c) vector?)
  goal : any/c
  start : exact-integer? = 0
  end : (or/c exact-integer? #f) = #f
  compare : (or/c #f (-> any/c any/c (or/c '= '< '>))) = #f
  mode : symbol? = 'any/=

Performs a binary search for goal in data and returns the index in the range start (inclusive) to end (exclusive) that satisfies the criteria specified by mode. If no such index exists, #f is returned.

The input, data from start to end, must be sorted in ascending order according to compare. If compare is #f, then standard numeric order is used.

If the result index is not #f, then it is an exact integer satisfying (<= start index) and (< index end). The result index is determined by the mode as follows:

'any/= — Returns any index in the given range such that (data index) is equal to goal according to compare. The result is not necessarily the least or greatest such index, but rather the first such index found during the binary search.
'least/=, 'greatest/= — Returns the least or greatest index, respectively, such that (data index) is equal to goal.
'greatest/<, 'greatest/<= — Returns the greatest index such that (data index) is strictly less than goal or less than or equal to goal, respectively.
'least/>, 'least/>= — Returns the least index such that (data index) is strictly greater than goal or greater than or equal to goal, respectively.

Examples:

> (define data (vector 1 3 4 4 4 9))
> (define (show-split v k)
    (printf "~s => ~s ~s ~s\n" k
            (vector-copy v 0 k)
            (vector-ref v k)
            (vector-copy v (add1 k))))
> (show-split data (binary-search data 4 #:mode 'any/=))
3 => #(1 3 4) 4 #(4 9)
> (show-split data (binary-search data 4 #:mode 'least/=))
2 => #(1 3) 4 #(4 4 9)
> (show-split data (binary-search data 4 #:mode 'greatest/=))
4 => #(1 3 4 4) 4 #(9)
> (show-split data (binary-search data 4 #:mode 'greatest/<))
1 => #(1) 3 #(4 4 4 9)
> (show-split data (binary-search data 4 #:mode 'greatest/<=))
4 => #(1 3 4 4) 4 #(9)
> (show-split data (binary-search data 4 #:mode 'least/>))
5 => #(1 3 4 4 4) 9 #()
> (show-split data (binary-search data 4 #:mode 'least/>=))
2 => #(1 3) 4 #(4 4 9)
> (binary-search data 2 #:mode 'least/=)
#f
> (show-split data (binary-search data 2 #:mode 'least/>))
1 => #(1) 3 #(4 4 4 9)

If end is #f and data is a vector, then the end index is (vector-length data). If end is #f and data is a procedure, then the end index is found by repeatedly doubling the search range until it contains the correct result. If the doubling phase does not succeed within a certain number of steps (currently 100), an error is raised.

> (define (floor-div4 n) (floor (/ n 4)))
> (binary-search floor-div4 5 #:mode 'least/=)
20
> (binary-search floor-div4 5 #:mode 'greatest/=)
23
> (binary-search floor-div4 5 #:mode 'least/>)
24

procedure
(binary-search-all data
goal
[ start
end
#:compare compare])
→
exact-integer? exact-integer?
  data : (or/c (-> exact-integer? any/c) vector?)
  goal : any/c
  start : exact-integer? = 0
   end : exact-integer?
= (and (vector? data) (vector-length data))
  compare : (or/c #f (-> any/c any/c (or/c '= '< '>))) = #f

Returns the range of indexes of data within start (inclusive) to end (exclusive) whose values are equal to goal.

The input, data from start to end, must be sorted in ascending order according to compare. If compare is #f, then standard numeric order is used.

The function returns (values starteq endeq) such that the following properties hold:

(<= start starteq endeq end)
For every index k such that (<= start k) and (< k starteq), (data k) is strictly less than goal according to compare.
For every index k such that (<= starteq k) and (< k endeq), (data k) is equal to goal according to compare.
For every index k such that (<= endeq k) and (< k end), (data k) is strictly greater than goal according to compare.

Given the partition of the input into less-than, equal, and greater-than ranges, it is straightforward to implement all of the modes supported by binary-search. Note that any of the ranges may be empty. In particular, if the input does not contain any values equal to goal, then starteq and endeq are equal and indicate the index where inserting goal would preserve ordering. (Beware, the insertion point is limited to the range from start to end, and it would preserve ordering for that section of data, but it may not preserve ordering on data’s full domain.)

Examples:

> (define data (vector 1 3 4 4 4 9))
> (define-syntax-rule (show-split2 v e)
    (let-values ([(starteq endeq) e])
      (printf "~s ~s => ~s ~s ~s\n"
              starteq endeq
              (vector-copy v 0 starteq)
              (vector-copy v starteq endeq)
              (vector-copy v endeq))))
> (show-split2 data (binary-search-all data 4))
2 5 => #(1 3) #(4 4 4) #(9)
> (show-split2 data (binary-search-all data 5))
5 5 => #(1 3 4 4 4) #() #(9)
> (show-split2 data (binary-search-all data 10))
6 6 => #(1 3 4 4 4 9) #() #()
> (show-split2 data (binary-search-all data 10 0 4))
4 4 => #(1 3 4 4) #() #(4 9)
> (define (floor-div4 n) (floor (/ n 4)))
> (binary-search-all floor-div4 5)
20
24