def upper_bound(haystack, needle, lo = 0, hi = None, cmp = None, key = None):
    """upper_bound(haystack, needle[, lo = 0[, hi = None[, cmp = None[, key = None]]]]) => n

Find \var{needle} via a binary search on \var{haystack}.  Returns the
non-negative index \var{N} of the element that immediately follows the
last match of \var{needle} if \var{needle} is found, else a negative
value \var{N} is returned indicating the index where \var{needle}
belongs with the formula "-\var{N}-1".

\var{haystack} - the ordered, indexable sequence to search.
\var{needle} - the value to locate in \var{haystack}.
\var{lo} and \var{hi} - the range in \var{haystack} to search.
\var{cmp} - the cmp function used to order the \var{haystack} items.
\var{key} - the key function used to extract keys from the elements.
"""
    if cmp is None: cmp = __builtin__.cmp
    if key is None: key = lambda x: x
    if lo < 0: raise ValueError( 'lo cannot be negative' )
    if hi is None: hi = len(haystack)

    val = None
    while lo < hi:
        mid = (lo + hi) >> 1
        val = cmp(key(haystack[mid]), needle)
        if val > 0:
            hi = mid
        else:
            lo = mid + 1
    if val is None: return -1
    elif val == 0: return lo
    elif lo > 0 and cmp(key(haystack[lo - 1]), needle) == 0: return lo
    else: return -1 - lo
upper_bound(haystack, needle[, lo = 0[, hi = None[, cmp = None[, key = None]]]]) => n

Find ar{needle} via a binary search on ar{haystack}.  Returns the
non-negative index ar{N} of the element that immediately follows the
last match of ar{needle} if ar{needle} is found, else a negative
value ar{N} is returned indicating the index where ar{needle}
belongs with the formula "-ar{N}-1".

ar{haystack} - the ordered, indexable sequence to search.
ar{needle} - the value to locate in ar{haystack}.
ar{lo} and ar{hi} - the range in ar{haystack} to search.
ar{cmp} - the cmp function used to order the ar{haystack} items.
ar{key} - the key function used to extract keys from the elements.

recipes/Python/577565_Binary_search_function/recipe-577565.py