二分法的應(yīng)用

李家琪 邱靜

摘要：本文我們主要論述了有關(guān)二分法在各個(gè)領(lǐng)域的一些應(yīng)用，在數(shù)學(xué)的求零點(diǎn)問題中，它幫助我們快速有效地求出問題解，在猜數(shù)字這種平常的生活游戲中，它大大降低了我們盲目猜的次數(shù)，而對于證明不等式，它更是以一種十分巧妙地轉(zhuǎn)換讓我們證明出結(jié)果;在計(jì)算機(jī)領(lǐng)域，它常被用于有序數(shù)據(jù)的排序以及查找;而在物理領(lǐng)域中，它同樣也是幫助我們簡化了探究問題解的方法;而在平時(shí)的生產(chǎn)生活中，它更是幫助我們提高效率的一種簡便方法。

關(guān)鍵詞：不等式證明;二分法檢索;勻變速直線運(yùn)動

1 二分法在數(shù)學(xué)中的應(yīng)用

二分法是我們分析解答數(shù)學(xué)問題的一個(gè)基本方法，我們知道，正確的使用二分法，能在解題時(shí)找到正確的思路或便捷的方法，化繁為簡。有些時(shí)候，一次的二分法不能解決問題，就需要多次使用。

1.1 二分法在數(shù)學(xué)中關(guān)于求零點(diǎn)的應(yīng)用

要使用二分法，首先要保證我們所使用的數(shù)列是升序或者降序排列的，這里我們?yōu)榱烁臃奖愕仃U明二分法的基本思想，將數(shù)列假設(shè)為升序排列。已知給定的數(shù)x，我們從數(shù)列的中間位置開始，將x與中間的數(shù)的值進(jìn)行比較，如果當(dāng)前位置的值等于x，則稱查找成功;若x的值小于當(dāng)前位置，則到數(shù)列的前半段中查找;若x大于當(dāng)前位置值則在數(shù)列的后半段中繼續(xù)查找，直到找到為止。

我們可以進(jìn)一步用數(shù)學(xué)的方法來解釋一下二分法。我們在日常解題的過程中比較常用到的便是二分法求零點(diǎn)即二分法求解方程的根。

我們先給出二分法在數(shù)學(xué)中的定義：對于在區(qū)間[a，b]上連續(xù)不斷且f（a）·f（b）<0的函數(shù)y=f（x），通過不斷把函數(shù)f（x）的零點(diǎn)所在區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法叫做二分法。

例1? 已知f（x）=2x2-3在[0，2]上有一個(gè)零點(diǎn)x，求x的值，精確到0.1。

在該題目中我們首先判斷函數(shù)在[0，2]上是遞增的，選取x=1帶入方程y=2x2-3，可得y=-1小于0，所以零點(diǎn)x的范圍縮小為[1，2]，再次帶入x=1.5進(jìn)入方程，得到y(tǒng)=1.5大于0，所以x的范圍繼續(xù)縮小到[1，1.5]之間，依次類推，可得x=1.2為2x2-3=0在[0，2]上的一個(gè)解，即x=1.2是f（x）在[0，2]上的一個(gè)零點(diǎn)，可見，用二分法來求零點(diǎn)是十分方便的。此處，我們只是粗略的介紹了二分法求零點(diǎn)的過程及二分思想，具體的關(guān)于解的精確問題此處暫且不談。

1.2 二分法在猜數(shù)字中的應(yīng)用

二分法一般應(yīng)用在數(shù)學(xué)中，便是求零點(diǎn)，但是除了這一用處之外，還有許多方面，例如我們常見的猜數(shù)游戲，也可以用二分法進(jìn)行。

由于27=128>100，所以可知，猜100以內(nèi)的整數(shù)x最多只要7次就可以猜中。

首先我們給定一個(gè)中點(diǎn)x=64，即26，問x是否大于64呢，如果這時(shí)候得到答案是肯定的，那么，我們便把范圍縮小到了65到100之間，再以96作為判定點(diǎn)，因?yàn)?6+25=96，若x還是大于96，那么我們再以98作為判斷值，因?yàn)?6+25+2=98，若x大于98，則再將x與99對比，若還不是，則x一定是100。

那么，若x不大于64呢，則范圍縮小到1到64之間，將25=32與x進(jìn)行比較大小，若x不大于32，我們再看x是否大于24=16，否定的話，再將x與8進(jìn)行比較是否大于8，還是否定，x與4比較是否大于4，得到否定，x與2比較是否大于2，得到否定，最后與1比較知x大于1，則x的值定為2。

以上的這個(gè)案例以2的指數(shù)冪的和作為猜數(shù)字的判斷分界點(diǎn)，在方法上給與了我們一定的啟示。

數(shù)學(xué)分析：當(dāng)?shù)谝粋€(gè)問題收到肯定回答，當(dāng)x大于64時(shí)，則我們將猜數(shù)的范圍縮小到了65至100中;若為否定回答，則范圍是1到64部分，這里我們第一次用二分法對一個(gè)大的范圍進(jìn)行刪減。我們以65到100為例，上例子中用二分法來猜出了結(jié)果。我們需要切記的是，在猜數(shù)時(shí)，一定要以若干個(gè)2的指數(shù)冪的和作為分界點(diǎn)猜數(shù)，這樣才能使猜數(shù)的次數(shù)最少。

1.3 二分法在證明不等式中的應(yīng)用

利用二分法，我們也可以巧妙地證明數(shù)學(xué)中的不等式。

例2? 已知三個(gè)正數(shù)a，b，c滿足2c>a+b，求證：

解析：仔細(xì)觀察所要證明的不等式的結(jié)構(gòu)，我們可以發(fā)現(xiàn)是一元二次方程x2-2cx+ab=0的兩個(gè)根，然后，我們構(gòu)造一個(gè)區(qū)間（）。

設(shè)f（x）=x2-2cx+ab，利用二分法的思想，要解出此問題，我們只要證明a在區(qū)間（）內(nèi)，即證明f（a）<0就可。由題干已知，2c>a+b，可得，f（a）=a2-2ac+ab=a（a-2c+b）<0。所以我們可知a在區(qū)間內(nèi)，即成立。

2 二分法在計(jì)算機(jī)語言中的運(yùn)用之二分法檢索

除了在數(shù)學(xué)上的應(yīng)用，二分法在計(jì)算機(jī)中的應(yīng)用也不可小覷。但在應(yīng)用的同時(shí)，我們也要注意運(yùn)用它所需滿足的條件。

二分法檢索又被稱為為折半查找法，我們運(yùn)用二分法來進(jìn)行檢索時(shí)，可以極大地提高我們的“辦事效率”，但使用它有一個(gè)前提，那就是線性表節(jié)點(diǎn)按照其關(guān)鍵字是有序排列的，即從小大到或從大到小按順序排列，并且它采用的是順序存儲結(jié)構(gòu)。

二分法檢索的基本過程為：設(shè)L[low..high]是當(dāng)前所要查找的區(qū)間，首先讓待查找的數(shù)據(jù)元素和線性表的中間節(jié)點(diǎn)mid=[（low+high）/2]的關(guān)鍵字比較，若比較相等，則表明查找成功，檢索結(jié)束;若待查找的數(shù)據(jù)元素小于中間結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在線性表的前半部分L[low..mid-1]進(jìn)行二分法檢索;若帶查找數(shù)據(jù)元素大于中間結(jié)點(diǎn)的關(guān)鍵字，則在在線性表的后半部分L[mid+1..high]進(jìn)行二分檢索，一直重復(fù)以上步驟直到查找到所要找的結(jié)點(diǎn)或確定確定表中沒有這樣的結(jié)點(diǎn)。以下給出案例：

例3? 已知含有10個(gè)數(shù)據(jù)元素的有序表為（僅列出元素項(xiàng)的關(guān)鍵字）：

（10，14，20，32，45，50，68，90，100，120）現(xiàn)在要在其中查找到關(guān)鍵字為20和95的數(shù)據(jù)元素。

根據(jù)二分檢索的基本思想，這里用指針low和high分別指示待查找元素所在范圍的上界和下界，指針mid指示區(qū)間的中間位置。在此例子中，low和high分別0和9，即[0..9]為待查找范圍。

此時(shí)，high<low，表明查找區(qū)間為空，說明檢索失敗，返回失敗信息。

下面為二分檢索法的非遞歸算法：（算法中使用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;? ? ? ? ? ?/*繼續(xù)在前半部分進(jìn)行二分檢索*/

else low=mid+1;

}

return -1;? ? ? ? ? /*當(dāng)low>high時(shí)表示查找區(qū)間為空，檢索失敗*/

3 小結(jié)

二分法的出現(xiàn)，給予了我們許多幫助，讓我們用“巧”辦法來解決實(shí)際問題。從函數(shù)求零點(diǎn)，方程求根，計(jì)算機(jī)中的數(shù)據(jù)查找，到實(shí)際生活中線路故障的排除，都能用二分法來解決。但我們在使用二分法時(shí)，要注意到二分法也是有限制的，切不可濫用，我們在應(yīng)用二分法的時(shí)候，要了解到應(yīng)用的情景以及局限，才能真正的正確地使用二分法，讓它為我們的生活帶來便利。

參考文獻(xiàn)：

[1] 單墫等. 普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書· 數(shù)學(xué)（ 必修1）. 南京： 江蘇教育出版社， 2007第3版

[2] 劉小明. 二分法思想的應(yīng)用.高中生之友.2011年09期 29-30

[3] 李云清，楊慶紅，揭安全.數(shù)據(jù)結(jié)構(gòu)（c語言版）.北京：人民郵電出版社，2014年第3版

[4] 李如虎. “ 逐差法”與“ 兩段法”.物理教學(xué). 上海： 華東師范大學(xué)出版社. 2009年5月

[5] 張維善等. 普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書· 物理（ 選修 3-1） . 北京： 人民教育出版社， 2007年第2版

[6] 周憲.現(xiàn)代性的五個(gè)悖論.北京：商務(wù)印書館，2005年

[7] 董殿雄.二分法求方程的近似解.鄭州.中學(xué)生數(shù)理化.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] 張維善等. 普通高中課程標(biāo)準(zhǔn)實(shí)驗(yàn)教科書· 物理（ 選修 3-4） . 北京： 人民教育出版社， 2007 年第2版