# [Python-Dev] Re: Re: lists v. tuples

Andrew Koenig ark@research.att.com
17 Mar 2003 10:17:33 -0500

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