CSES - Largest distance

A list contains nn integers in the range 1k1\dots k. We want to add another integer in the range 1k1\dots k to the list so that the distance of the new number to the nearest old number is as large as possible. What is this distance?

The time complexity of the algorithm should be O(nlogn)O(n \log n).

In a file distance.py, implement a function find that returns the maximal distance.

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

Explanation: In the first case, the result is 33, because we can add the number 55 or 66 so that the distance (to 22 or 99) is 33. It is not possible to add a number so that the distance is 44 or more.