字节跳动去年秋招的一个笔试题

某视频网站有N个视频，每个视频时长为秒。产品经理找到你，希望你帮忙在其中插入M个广告。
一个视频里的两个广告必须间隔一段时间，当然间隔时间可以为0。
为了用户体验，他希望这个间隔时间尽可能长。为了方便实现，间隔时间是一个整数。
请你帮忙计算一下，这个间隔时间最大可以设置为多少秒呢？如果不能插入广告，则输出0。

输入

第一行有两个整数N, M（1<=N<=100000, N<M<=5000000）
第二行有N个整数，表示视频的时长(1<=<=1e9)

输出

一个整数，表示最大的间隔时间

样例输入

3 9
90 100 120

样例输出

45

说明

最长广告间隔为45秒。第一个视频时长90秒，可以在第0秒，第45秒，第90秒分别插入一个广告，总共3个广告。

分析

这个题目是寻找在一定条件限制下的最大值，可以用二分法快速解。

完整代码可以在下头评论我发给你:)
我这里还有字节其他几场的笔试题目，也一并发你