Suurin etäisyys

Listalla on $n$ kokonaislukua väliltä $1\dots k$. Listalle halutaan lisätä uusi kokonaisluku väliltä $1\dots k$, jonka etäisyys lähimpään listalla valmiiksi olevaan lukuun on mahdollisimman suuri. Mikä on tämä etäisyys?

Algoritmin aikavaativuuden tulee olla $O(n \log n)$.

Toteuta tiedostoon distance.py funktio find, joka ilmoittaa suurimman mahdollisen etäisyyden.

def find(t, k):
    # TODO

if __name__ == "__main__":
    print(find([1, 2, 9], 11)) # 3
    print(find([2, 1, 3], 3)) # 0
    print(find([7, 4, 10, 4], 10)) # 3
    print(find([15, 2, 6, 4, 18], 20)) # 4
    print(find([41222388, 392676742, 307110407, 775934683, 25076911], 809136843)) # 191628970

Selitys: Ensimmäisessä tapauksessa vastaus on $3$, koska listalle voidaan lisätä luku $5$ tai $6$, jolloin etäisyys on $3$ (lukuun $2$ tai $9$). Ei ole mahdollista lisätä lukua niin, että etäisyys olisi $4$ tai enemmän.