[Python-Dev] Re: Re: lists v. tuples (original) (raw)

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