思路
求最值的算法题一般是贪心或者动规，但也有其他的情况，比如既找不到局部最优也写不出递推公式，这个时候或许可以尝试一下二分。
二分的思路很简单，即面向答案编程。它不关心具体的操作过程，而是先确定答案的范围，二分得到中间值，判断当前值是否满足要求，继续二分直到找到结果。
例子
lc5219. 每个小孩最多能分到多少糖果
https://leetcode-cn.com/problems/maximum-candies-allocated-to-k-children/.
给你一个下标从0开始的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的子堆 ，但无法再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到相同数量的糖果。每个小孩可以拿走至多一堆糖果，有些糖果可能会不被配。
返回每个小孩可以拿走的 最大糖果数目 。
这题我开始的想法是排序、找出第k个最大值作为基准，然后将最大值切一部分加到较小值上，不断增加基准值。这样很复杂，也不知道该怎么分配。所以，pass。
还是来看二分。
既然是面向答案编程，那就忽略过程，首先看答案的范围。小朋友获得的糖果最少为1个，最多为糖果之和整除k得到的结果，即恰好能平分的情况。
二分的left和right确定了，接下来就是熟悉的步骤了。对于当前值mid，我们要判断给每个小朋友分mid个糖果是否可行。怎么做呢？直接让每一堆的糖果整除mid，把结果加起来，看是否大于等于k即可。然后根据判断结果缩小答案范围。
代码如下：
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
l,r=0,sum(candies)//k
while l<r:
mid=l+(r-l+1)//2
temp=0
for candy in candies:
temp+=candy//mid
if temp<k:
r=mid-1
else:
l=mid
return l
lc2187. 完成旅途的最少时间
https://leetcode-cn.com/problems/minimum-time-to-complete-trips/.
给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成一趟旅途所需要花费的时间。
每辆公交车可以连续完成多趟旅途，也就是说，一辆公交车当前旅途完后，可以立马开始下一趟旅途。每辆公交车独立运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表示所有公交车总共需要完成的旅途数目。请你返回完成至少 totalTrips 趟旅途需要花费的最少时间。
这题同理，我们不要去纠结让哪些车去运，直接考虑需要的最少时间是多少。
答案的范围是[1,min(time)*totalTrips]，最小值自然是1，最大值即让花费时间最短的车运完全部旅途需要的总时间。
然后二分，判断当前值是否满足要求，这里的标准是在当前给定的时间下，所有的车能不能运满toalTrips次，同样是一个依次整除再求和的操作。
代码如下：
class Solution(object):
def minimumTime(self, time, totalTrips):
"""
:type time: List[int]
:type totalTrips: int
:rtype: int
"""
l,r=1,min(time)*totalTrips
while l<r:
mid=(l+r)//2
temp=0
for item in time:
temp+=mid//item
if temp<totalTrips:
l=mid+1
else:
r=mid
return l
小红书笔试题：选礼物
薯队长最近在参加了一个活动，在活动结束后，可以挑选一些礼物留作纪念,主办方提供了n个礼物以供挑选，每个礼物有一个虚拟的价值，范围在0-10^9之间，薯队长可以从中挑选k个礼物(2<=k<=n)。薯队长不想选价值过近的礼物，所以薯队长找到您帮忙，看从中选k个礼物，其中价值最接近的两件礼物之间相差值尽可能大，输出价值最接近的两件礼物之间相差值的最大值。
示例：
输入： nums=[2,3,5,6,9]，k=3
输出： 3
解释： 选择价值为2、9、5的这3个礼物，价值最接近的两个礼物是2和5，相差3，是最大的一个结果。
这题翻译一下就是在数组里找k个值，让它们的值尽可能分散，然后将这k个值之间的最小间隔输出。
我们想一下，如果是找两个值，直接排序取首尾两个数即可。如果是取三个，再加一个值居中的。但如果是多个呢？情况就变得很复杂了，找不到一个可行的策略。
那就上二分！
依然是把答案（最小间隔）作为二分对象。答案的范围为[0,nums[-1]-nums[0]]，注意这里的nums是排序后的。
接下来判断当前值是否满足条件，也就是看当最小间隔为mid时，能不能在数组中找到k个值。这个很简单，从小到大按照间隔大于等于mid依次找k个值就行。
代码如下：
def getMinDistance(nums,k):
nums.sort()
def check(nums,k,interval):#找出nums中以interval为最小间隔的序列，看长度是否大于等于k
cnt=1
last=nums[0]
for num in nums:
if num-last>=interval:
cnt+=1
last=num
return cnt>=k
#二分求最小间隔
l,r=0,nums[-1]-nums[0]
while l<r:
mid=(l+r+1)//2
if check(nums,k,mid):
l=mid
else:
r=mid-1
return l
总结
使用场景
二分法求最值一般用在操作复杂，找不到规律的情况下。这个时候直接面向答案进行二分可以达到另辟蹊径的效果。
二分步骤
- 确定答案的范围
- 判断当前值是否满足条件
- 缩小范围