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

[Andrew Koenig]

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