def binprobe(left, right, index_exists):
    """ Searches the last existing entry in a
        "sequence of indices" from left to right (including).
        Assumes that "left" starts on an existing entry,
        and left <= right, and left >= 0, and right >= 0.
        The index "right" may either be the last existing entry,
        or points to an entry that doesn't exist.
        @param left Start index
        @param right End index
        @param index_exists Function that checks whether a 1-based index
                             is in or out of the sequence (exists or not).
        @return 1-based index of the last existing entry, in
                 the given interval
    """
    while ((right - left) > 1):
        middle = left + (right - left) // 2
        if not index_exists(middle):
            right = middle - 1
        else:
            left = middle

    # Special handling for when only the two
    # last IDs are left...or a single one (left=right).
    if index_exists(right):
        return right
    return left