def binary_search(a, k):
    """
    Do a binary search in an array of objects ordered by '.key'

    returns the largest index for which:  a[i].key <= k

    like c++: a.upperbound(k)--
    """
    first, last = 0, len(a)
    while first < last:
        mid = (first + last) >> 1
        if k < a[mid].key:
            last = mid
        else:
            first = mid + 1
    return first - 1