二分法的应用

李家琪 邱静

摘要：本文我们主要论述了有关二分法在各个领域的一些应用，在数学的求零点问题中，它帮助我们快速有效地求出问题解，在猜数字这种平常的生活游戏中，它大大降低了我们盲目猜的次数，而对于证明不等式，它更是以一种十分巧妙地转换让我们证明出结果;在计算机领域，它常被用于有序数据的排序以及查找;而在物理领域中，它同样也是帮助我们简化了探究问题解的方法;而在平时的生产生活中，它更是帮助我们提高效率的一种简便方法。

关键词：不等式证明;二分法检索;匀变速直线运动

1 二分法在数学中的应用

二分法是我们分析解答数学问题的一个基本方法，我们知道，正确的使用二分法，能在解题时找到正确的思路或便捷的方法，化繁为简。有些时候，一次的二分法不能解决问题，就需要多次使用。

1.1 二分法在数学中关于求零点的应用

要使用二分法，首先要保证我们所使用的数列是升序或者降序排列的，这里我们为了更加方便地阐明二分法的基本思想，将数列假设为升序排列。已知给定的数x，我们从数列的中间位置开始，将x与中间的数的值进行比较，如果当前位置的值等于x，则称查找成功;若x的值小于当前位置，则到数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

我们可以进一步用数学的方法来解释一下二分法。我们在日常解题的过程中比较常用到的便是二分法求零点即二分法求解方程的根。

我们先给出二分法在数学中的定义：对于在区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断把函数f（x）的零点所在区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法。

例1  已知f（x）=2x2-3在[0，2]上有一个零点x，求x的值，精确到0.1。

在该题目中我们首先判断函数在[0，2]上是递增的，选取x=1带入方程y=2x2-3，可得y=-1小于0，所以零点x的范围缩小为[1，2]，再次带入x=1.5进入方程，得到y=1.5大于0，所以x的范围继续缩小到[1，1.5]之间，依次类推，可得x=1.2为2x2-3=0在[0，2]上的一个解，即x=1.2是f（x）在[0，2]上的一个零点，可见，用二分法来求零点是十分方便的。此处，我们只是粗略的介绍了二分法求零点的过程及二分思想，具体的关于解的精确问题此处暂且不谈。

1.2 二分法在猜数字中的应用

二分法一般应用在数学中，便是求零点，但是除了这一用处之外，还有许多方面，例如我们常见的猜数游戏，也可以用二分法进行。

由于27=128>100，所以可知，猜100以内的整数x最多只要7次就可以猜中。

首先我们给定一个中点x=64，即26，问x是否大于64呢，如果这时候得到答案是肯定的，那么，我们便把范围缩小到了65到100之间，再以96作为判定点，因为26+25=96，若x还是大于96，那么我们再以98作为判断值，因为26+25+2=98，若x大于98，则再将x与99对比，若还不是，则x一定是100。

那么，若x不大于64呢，则范围缩小到1到64之间，将25=32与x进行比较大小，若x不大于32，我们再看x是否大于24=16，否定的话，再将x与8进行比较是否大于8，还是否定，x与4比较是否大于4，得到否定，x与2比较是否大于2，得到否定，最后与1比较知x大于1，则x的值定为2。

以上的这个案例以2的指数幂的和作为猜数字的判断分界点，在方法上给与了我们一定的启示。

数学分析：当第一个问题收到肯定回答，当x大于64时，则我们将猜数的范围缩小到了65至100中;若为否定回答，则范围是1到64部分，这里我们第一次用二分法对一个大的范围进行删减。我们以65到100为例，上例子中用二分法来猜出了结果。我们需要切記的是，在猜数时，一定要以若干个2的指数幂的和作为分界点猜数，这样才能使猜数的次数最少。

1.3 二分法在证明不等式中的应用

利用二分法，我们也可以巧妙地证明数学中的不等式。

例2  已知三个正数a，b，c满足2c>a+b，求证：

解析：仔细观察所要证明的不等式的结构，我们可以发现是一元二次方程x2-2cx+ab=0的两个根，然后，我们构造一个区间（）。

设f（x）=x2-2cx+ab，利用二分法的思想，要解出此问题，我们只要证明a在区间（）内，即证明f（a）<0就可。由题干已知，2c>a+b，可得，f（a）=a2-2ac+ab=a（a-2c+b）<0。所以我们可知a在区间内，即成立。

2 二分法在计算机语言中的运用之二分法检索

除了在数学上的应用，二分法在计算机中的应用也不可小觑。但在应用的同时，我们也要注意运用它所需满足的条件。

二分法检索又被称为为折半查找法，我们运用二分法来进行检索时，可以极大地提高我们的“办事效率”，但使用它有一个前提，那就是线性表节点按照其关键字是有序排列的，即从小大到或从大到小按顺序排列，并且它采用的是顺序存储结构。

二分法检索的基本过程为：设L[low..high]是当前所要查找的区间，首先让待查找的数据元素和线性表的中间节点mid=[（low+high）/2]的关键字比较，若比较相等，则表明查找成功，检索结束;若待查找的数据元素小于中间结点的关键字，则继续在线性表的前半部分L[low..mid-1]进行二分法检索;若带查找数据元素大于中间结点的关键字，则在在线性表的后半部分L[mid+1..high]进行二分检索，一直重复以上步骤直到查找到所要找的结点或确定确定表中没有这样的结点。以下给出案例：

例3  已知含有10个数据元素的有序表为（仅列出元素项的关键字）：

（10，14，20，32，45，50，68，90，100，120）现在要在其中查找到关键字为20和95的数据元素。

根据二分检索的基本思想，这里用指针low和high分别指示待查找元素所在范围的上界和下界，指针mid指示区间的中间位置。在此例子中，low和high分别0和9，即[0..9]为待查找范围。

此时，high<low，表明查找区间为空，说明检索失败，返回失败信息。

下面为二分检索法的非递归算法：（算法中使用seqlist.h中定义的顺序查找表）

#include “seqlist.h”

int binsearch1（seqlist l，datatype key）

{   int low=0，high=l.len-1，mid;

While （low<=high）

{   mid=（low+high）/2;     /*二分*/

if （l.data[mid]==key）  return mid;    /*检索成功返回*/

if（l.data[mid]>key）

high=mid-1;           /*继续在前半部分进行二分检索*/

else low=mid+1;

}

return -1;          /*当low>high时表示查找区间为空，检索失败*/

3 小结

二分法的出现，给予了我们许多帮助，让我们用“巧”办法来解决实际问题。从函数求零点，方程求根，计算机中的数据查找，到实际生活中线路故障的排除，都能用二分法来解决。但我们在使用二分法时，要注意到二分法也是有限制的，切不可滥用，我们在应用二分法的时候，要了解到应用的情景以及局限，才能真正的正确地使用二分法，让它为我们的生活带来便利。

参考文献：

[1] 单墫等. 普通高中课程标准实验教科书· 数学（ 必修1）. 南京： 江苏教育出版社， 2007第3版

[2] 刘小明. 二分法思想的应用.高中生之友.2011年09期 29-30

[3] 李云清，楊庆红，揭安全.数据结构（c语言版）.北京：人民邮电出版社，2014年第3版

[4] 李如虎. “ 逐差法”与“ 两段法”.物理教学. 上海： 华东师范大学出版社. 2009年5月

[5] 张维善等. 普通高中课程标准实验教科书· 物理（ 选修 3-1） . 北京： 人民教育出版社， 2007年第2版

[6] 周宪.现代性的五个悖论.北京：商务印书馆，2005年

[7] 董殿雄.二分法求方程的近似解.郑州.中学生数理化.2010年第9期7-8

[8] Hopcroft A， Ullman. The Design and Analysis of Computer Algorithms [M]. Addison Wesley， 1974.

[9] 5 Kozen D C. The Design and Analysis of Algorithms[M]. Berlin： Springer-Verlag， 1992.

[10] 张维善等. 普通高中课程标准实验教科书· 物理（ 选修 3-4） . 北京： 人民教育出版社， 2007 年第2版