Tim> For example, probing a vanilla binary search tree needs to stop
Tim> when it hits a node with key equal to the thing searched for, or
Tim> move left or right when != obtains.
The binary-search routines in the C++ standard library mostly avoid
having to do != comparisons by defining their interfaces in the
following clever way:
binary_search returns a boolean that indicates whether the
value sought is in the sequence. It does not
say where that value is.
lower_bound returns the first position ahead of which
the given value could be inserted without
disrupting the ordering of the sequence.
upper_bound returns the last position ahead of which
the given value could be inserted without
disrupting the ordering of the sequence.
equal_range returns (lower_bound, upper_bound) as a pair.
In Python terms:
binary_search([3, 5, 7], 6) would yield False
binary_search([3, 5, 7], 7) would yield True
lower_bound([1, 3, 5, 7, 9, 11], 9) would yield 4
lower_bound([1, 3, 5, 7, 9, 11], 8) would also yield 4
upper_bound([1, 3, 5, 7, 9, 11], 9) would yield 5
equal_range([1, 1, 3, 3, 3, 5, 5, 5, 7], 3)
would yield (2, 5).
If you like, equal_range(seq, x) returns (l, h) such that all the
elements of seq[l:h] are equal to x. If l == h, the subsequence is
the empty sequence between the two adjacent elements with values that
bracket x.
These definitions turn out to be useful in practice, and are also
easy to implement efficiently using only < comparisons.
--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4