二分法的應用

李家琪 邱靜

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

關鍵詞：不等式證明;二分法檢索;勻變速直線運動

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版