[科普中國(guó)]-二分法

定義

二分法（Bisection method） 即一分為二的方法. 設(shè)[a，b]為R的閉區(qū)間. 逐次二分法就是造出如下的區(qū)間序列([an，bn])：a0=a，b0=b，且對(duì)任一自然數(shù)n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中點(diǎn).2

典型算法算法：當(dāng)數(shù)據(jù)量很大適宜采用該方法。采用二分法查找時(shí)，數(shù)據(jù)需是排好序的。

基本思想：假設(shè)數(shù)據(jù)是按升序排序的，對(duì)于給定值key，從序列的中間位置k開始比較，

如果當(dāng)前位置arr[k]值等于key，則查找成功；

若key小于當(dāng)前位置值arr[k]，則在數(shù)列的前半段中查找,arr[low,mid-1]；

若key大于當(dāng)前位置值arr[k]，則在數(shù)列的后半段中繼續(xù)查找arr[mid+1,high]，

直到找到為止,時(shí)間復(fù)雜度:O(log(n))3。

求法給定精確度ξ,用二分法求函數(shù)f(x)零點(diǎn)近似值的步驟如下:

1 確定區(qū)間[a,b],驗(yàn)證f(a)·f(b)= 0); // bad input or f(a) * f(b) >= 0do{c = (a + b) / 2.0; // c is the average number of a and bif (f(a) * f(c) =end,則結(jié)束查找；否則，向下繼續(xù)。

3.若a[mid]x，說明待查找的元素值只可能在比中項(xiàng)元素小的范圍內(nèi)，則把mid-1的值賦給end，并重新計(jì)算mid，轉(zhuǎn)去執(zhí)行步驟2。

代碼：

#include

#define N 10

using namespace std;

int main()

{

int a[N],front,end,mid,x,i;

cout