二分再也不用担心搞不清楚了，一文理解透二分

原文链接：分治第三讲：揭开二分神秘面纱

上一讲中提到二分细节是魔鬼分治第二讲：二分答案之砍树问题，关于二分，经常有同学搞不清楚【while(left<right)?】和 【while(left?<= right）】，也搞不清楚什么时候用right=mid，什么时候用right=mid-1，可不可以用left=mid，这篇文章就来回答上面的所有疑问，将我对二分的理解分享给大家，供大家参考。

假设二分最终要找的最优解为x，那么二分的时候，有两种理解方式，理解方式不一样，写出来的代码也不一样。

理解一：当前最优解保留在区间中

所求最优解x一直保留在区间[left, right]中，如果这样理解，那么我们的循环条件为while(left < right)，这样，当left 等于 right时，此时[left, right]区间中只有一个元素，该区间中的唯一元素left一定为所求最优解x（因为当前最优解永远保留在区间中），由于在二分中，防止陷入死循环，不可以出现left = mid（下面代码有解释为什么会陷入死循环）, 因此这种方式针对【最大值最小问题】没有风险，但是针对【最小值最大问题】，那么这种理解方式，势必会出现left = mid代码，这样会让你的代码存在陷入死循环的风险；

对于【最大值最小问题】，代码如下：

while(left < right) {
  mid = left + (right-left)/2;
  if(check(mid)) {  // mid为一个可能解，保留在区间中
    right = mid;  // 本行代码可以将可能解mid保留在区间中
  } else {  // 否则mid不是可能解
    left = mid+1;  // 解在右区间，缩小区间
  }
}
cout << left << endl;  // 最优解为left

对于【最小值最大问题】，代码如下（bad code, 勿使用）：

while(left < right) {
  mid = left + (right-left)/2;
  if(check(mid)) { // mid为一个可能解，保留在区间中
    left = mid;  // 注意，危险操作，不要使用，有死循环的风险。
  } else {
    right = mid-1;
  }
}
cout << left << endl;  // 最优解为left

对于上面代码，为何会有死循环的风险，举个例子，比如此时left 等于 2, right 等于 3;?计算得到mid 等于 2(c++向下取整)，执行第三行check(mid)时，如果返回true，那么此时执行left = mid，mid为2，因此更新left依然为2，如此下去，left一直等于2，right等于3，while循环无法结束，因此陷入死循环。

理解二：当前最优解不保留在区间中

所求最优解x不在区间[left, right]中，使用临时变量ans保存当前可能解。那么此时区间中未保留答案x，所以当区间长度为1，即left等于right时，依然需要判断该元素是否为最优解x。

对于【最大值最小问题】，代码如下：

while(left <= right) {
  mid = left + (right-left)/2;
  if(check(mid)) {   // 当前mid为可能解
    ans = mid;  // 保存起来可能解
    right = mid-1;  // 当前最优解保存在ans中，所以不需要把当前解mid保留在区间中
  } else {
    left = mid+1;
  }
}
cout << ans << endl;  // 最优解为ans

对于【最小值最大问题】，代码如下：

while(left <= right) {
  mid = left + (right-left)/2;
  if(check(mid)) { // 返回true，则当前mid是可能解
    ans = mid;  // 保存起来可能解
    left = mid+1;  // 当前最优解保存在ans中，所以不需要把当前解mid保留在区间中
  } else {
    right = mid-1;
  }
}
cout << ans << endl;  // 最优解为ans

补充一点

上面求解mid的时候，用的是mid = left + (right-left)/2; 而不是mid?=?(left+ right)/2;?虽然从数学角度来说，两者一样，但是从编程角度来说，mid?=?(left+ right)/2;有越界的风险，导致求解的mid错误，所以以后计算mid的时候，强制统一用mid = left + (right-left)/2;?更加安全。

比如我们int的最大值为2^31 - 1，那么如果left =?100, right =?2^31-2，如果用mid = left + (right-left)/2;可以安全计算出mid,但是如果用mid?=?(left + right)/2，其中left+right已经超过了int的最大值2^31 - 1，所以一定会得到错误的答案。因此以后计算mid的时候，强制统一用mid = left + (right-left)/2;?更加安全。

总结

while(left < right)?

表示将最优解保留在当前区间[left, right]中，因此当循环结束后，区间一定会留下一个元素，该元素一定为最优解；因为需要保留最优解在区间中，所以一定会有right=mid（最大值最小问题）或者left=mid（最小值最大问题），前面分析left=mid有风险，所以对于最小值最大问题，不要使用这种方式；

while(left <= right)?

表示将最优解不保留在当前区间[left, right]中，因此当循环结束后，区间一定为空，即left > right，即使区间中只剩一个元素，也要判断是否为最优解，直到区间为空，因为最优解不保留在区间中，所以需要一个变量ans来保存最优解，所以一定会有right=mid-1（最大值最小问题）或者left=mid+1（最小值最大问题），没有风险，对于两类问题均可使用；

往期文章推荐

分治第一讲：归并排序及求解逆序对

分治第二讲：二分答案之砍树问题