You are given a list of integers from the range 1 \dots k. The task is to add a new integer from the range 1 \dots k to the list so that the distance to the nearest other integer on the list is as big as possible. How big is that distance?
You may assume that the list contains at most 10^5 integers and that k is at most 10^9. The goal is an algorithm with time complexity O(n) or O(n \log n).
In a file distance, implement a function find that returns the biggest distance possible.
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: Each integer in the range 1 \dots 11 is at most a distance 3 from some integer on the list [1, 2, 9]. One such integer is 5, which is distance 3 from 2. Another possible choice is 6, which is distance 3 from 9. The list [2, 1, 3] contains every integer in the range 1 \dots 3. Thus the biggest distance is 0.