【Python数据结构与算法】二分法----Aggressive cows好斗的奶牛

题目：好斗的奶牛

农民约翰建造了一个新的长谷仓，有 N （2 <= N <= 100,000） 个畜栏。摊位位于位置 x1,…,xN （0 <= 习 <= 1,000,000,000） 处的一条直线。
他的 C （2 <= C <= N） 奶牛不喜欢这种牛舍布局，一旦被放入畜栏，它们就会变得相互攻击。为了防止奶牛互相伤害，FJ希望将奶牛分配到畜栏，以便它们中的任何两个之间的最小距离尽可能大。最大最小距离是多少。
输入

• Line 1: Two space-separated integers: N and C

• 第 1 行：两个空格分隔的整数：N 和 C

• Lines 2…N+1: Line i+1 contains an integer stall location, xi

• 第 2…N+1 行：第 i+1 行包含整数停档位置，习

输出

• Line 1: One integer: the largest minimum distance
• 第 1 行：一个整数：最大最小距离

样例输入

5 3
1
2
8
4
9

样例输出

3

AC代码

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
FJ 可以将他的 3 头奶牛放在 1、4 和 8 位置的畜栏中，最小距离为 3。

Huge input data,scanf is recommended.
输入数据量大，建议使用scanf。

N,C = map(int,input().split())
x = [] 
for i in range(N):
	x.append(int(input()))
x.sort()
def valid(d): 
	prevPos = x[0] 
	totalDone = 1  
	for i in range(1,N):
		if x[i] - prevPos >= d:
			prevPos = x[i]  
			totalDone += 1
			if totalDone == C:
				return True
	return False
L,R = 1, 1000000000//(C-1) + 1
best = 0
while L <= R:
	D = L + (R - L)//2
	if valid(D):
		best = D
		L = D + 1
	else:
		R = D - 1
print(best)