Annettuna on lista kokonaislukuja, jotka kaikki ovat väliltä 1\dots k. Listalle halutaan lisätä uusi kokonaisluku väliltä 1\dots k, jonka etäisyys lähimpään listalla jo valmiiksi olevaan lukuun on mahdollisimman suuri. Kuinka suuri tuo etäisyys voi korkeintaan olla?
Voit olettaa, että listalla on korkeintaan 10^5 lukua ja k on korkeintaan 10^9. Tavoitteena on, että algoritmin aikavaativuus on O(n) tai 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: Jokainen kokonaisluku väliltä 1\dots 11 on korkeintaan 3:n päässä jostain listan [1, 2, 9] luvusta. Yksi tällainen luku on esimerkiksi 5, joka on kolmen päässä sitä lähimmästä luvusta 2. Luku 6 puolestaan on kolmen päässä luvusta 9. Jokainen luku väliltä 1\dots 3 löytyy jo valmiiksi listalta [2, 1, 3]. Siksi suurin etäisyys on 0.