BUPT大一上学期第三次机考E题核心部分题解 &&　二分法讲解。

## 二分！二分！
## 引入背景
同学们有没有为上周第三次机考E题困扰呢？  
大家都能读懂题目，但是很多同学就很苦恼了：明明我答案是对的，但是为什么我超出时间限制（TLE）了呢？  
这是因为大家设计的程序的时间复杂度太高了，在碰到大数据的时候程序无法在规定时间内完成所有运算。  
那么这一篇文章就来给大家介绍一种更优的搜索答案的方案————它就是二分查找！
## 疑惑&解惑
二分？是那个数学高中必修I上、高数上讲的那个二分法吗？  
对~！没错就是它！  
蛤？二分不是用来找函数近似零点的吗？怎么就成了查找答案了？  
nope，二分的功能不只是那一个，它可强大了。在计算机上，我们目前的主要应用是用来二分查找答案。  
## 正题
二分查找，是因为单个查找的时间复杂度太高，让程序查找答案的效率低下，而出现用来替代单步查找的一种方法。它是一种思想，而不能叫做一种算法。  
对于二分查找的题目，一般都有一个明显的特征：判断这个解是否能满足所有的题目条件。同学们在设计第三次机考E题的时候，就是逐步判断每一个解是否能满足题意的。其实这种方法从理论上来说是正确的，但是它却做了一些不必要的工作。  
我们就以E题来讲解一下二分查找的思路。  
首先，我们能确定，最佳答案ans（给战士补充的最大能量）一定在范围1到max{$a_i$}中,其中$a_i$表示第i个能量瓶所含的能量值。  
那么我们设答案左区间l = 1，右区间r = max{$a_i$},然后我们用去检索答案区间的中间值mid = $(l + r) / 2$是否能够满足题意。  如果mid能够满足题意，那么说明当前能量值是可行方案，我们就记录下当前的mid的值作为当前答案存入ans，`ans = mid;`，然后去检索更大的值是否可行，也就是将mid+1赋值给l，继续去搜索。 
当然，如果mid不能够满足题意，那么说明当前的能量值是不可行的方案，我们就不用记录当前的答案，然后我们去搜索更小的答案是否可能能行，也就是将mid-1赋值给r。  
这样做下去，我们的答案区间在不断缩小，我们也就能够不断逼近最佳的解。直到我们将区间长度缩小为0，也就是$r<l$,那么当前ans中记录的值就是我们要求的最佳答案了。  
以上过程我们通常使用while循环去做，直到满足$r<l$，我们就跳出while循环，此时ans中存储的值便是我们要的答案。  
那么接下来我们附上核心部分代码（check函数就是判断这个答案是否可行，这个就不放出来了）：

while(l <= r){
        mid = (r + l)  / 2;
        if(check(mid)){
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    
总结一下，二分查找的核心思路是：确定答案所在区间$l，r$
，计算区间中间值$mid$，检查中间值$mid$是否满足题意(也就是我们代码里的check函数（这个函数需要大家自行编写）)，若满足，则记录答案$ans$ =  $mid$，如不满足则不记录答案，然后将区间缩小（至于往哪边缩小要看题目，可以去luogu上看看类似的简单二分题）。直到区间长度为0，跳出while循环，输出答案$ans$。 
如果我们单步检索答案，我们的程序的时间复杂度是O(m*max{$a_i$}),但如果我们使用二分查找的话，我们的程序的时间复杂度就成为了O(m*$log_2max{a_i}$)了，这样时间复杂度就下降了不少！  
## 需要注意的地方
并不是所有检索答案的题目都能使用二分查找的。我们称可以使用二分查找的题目的数学模型"满足二分性"。事实上确实是有一些题目是不满足二分性的。  
满足二分性的定义：我们称一个题目的数学模型满足二分性，当且仅当找到一个值满足题目条件，且小于它的所有值或者大于它的所有值都能满足题目条件。  
如果不满足上述的条件，那么我们说这个题目不满足二分性，也就不能使用二分查找来优化检索答案。这样的题目有很多，而且大多数会长得很像使用二分的题目（比如求XXX的最大值的理论最小值，大概95%的题目是用二分查找，剩下5%的题目是用贪心思想或者其他的算法去做），这时候就需要大家仔细判断了。  
很显然，我们机考的E题是一个满足二分性的题目，是可以进行二分查找的。

## 后言
好啦，关于二分查找的讲解就到这里啦，当然其实C++里面是有二分查找的库函数模板的，但是还是推荐大家使用自己手写的二分查找，因为这个二分查找更加灵活。  
大家如果想练习二分查找的题目的话，可以到luogu上面直接找题目分类->二分 里面的题目。  
最后祝大家计导期末考顺利8。

Icontofig 's Blog

公告板

最近发表

管理

友情链接

导航

最近发表

友情链接

Icontofig 's Blog

公告板

最近发表

标签云

管理

友情链接

导航

最近发表

友情链接