二分算法是分治算法的一种，注意分治算法有很多子类，比如：折半查找、二分算法，三分算法、分形问题等，第八章的很多排序算法也属于分治算法。
二分算法是把问题"解空间"一分为二的算法。它要求答案可以通过枚举的方式解决，同时解空间具有单调性，比如本题目飞船的跳跃能力，如果X能力可以成功，那么X+1、X+2......都可以成功，这就是单调性。
解题方法是先设定解空间的范围，比如本题目飞船的能力区间可以设定为[0,a[n]]，显然飞船如果具备一次跳到终点a[n]的能力，那么它一定能完成任务。
算法模板：
定义当前解区间为[L,R],求出中点mid，无论mid是否满足条件，都要根据题意决定下一次区间范围，直到区间长度小于1位置。最后best（备胎）中存储的是满足条件的极值。
int L=0,R=2e9,mid,best=0;
while(L<=R)/**< */
{
? ? mid=(L+R)/2;
? ? if(check(mid))
? ? ? ? ? best=mid,R=mid-1;
? ? else
? ? ? ? ? L=mid+1;
}
cout<<best<<endl;
本题目唯一难点就是如何判断k天能否到达，此处使用了双指针法，pre和和i同步前进。细节写在代码注释中，读者根据代码自行研读。
#include <iostream>
using namespace std;
int n,m,key,a[100005];
bool check(int x)/**< 跳能力是x，跳几次？ */
{ /**< 双指针表示跳跃行为，计算后，跳跃的起点pre，跳跃终点i-1 */
int pre=0,c=0;
for(int i=1;i<=n;i++)
{
if(a[i]-a[i-1]>x)
return false;
if(a[i]-pre>x)
{ /**< 最多能跳到i-1，跳到i就超过能力x了，pre--->i-1 */
pre=a[i-1];
c++;
i--;
}
}
c++;/**< 最后加一次是因为上面循环跳到a[n]时没有计算次数 */
return c<=m;
}
int main()
{
int i,j,q;
cin>>n>>m;
for(i=1; i<=n; i++)
cin>>a[i];
int L=1,R=2E9,mid,best=0;
while(L<=R)/**<当区间不为空时 */
{
mid=(L+R)/2;
if(check(mid)) /**< 如果中点满足条件，先记录这个值，然后将区间缩小为[L,mid-1] */
best=mid,R=mid-1;
else
L=mid+1; /**< 中点不满足条件，这个值显然不够大，区间缩小为[mid+1,R] */
}
cout<<best<<endl;
return 0;
}
