二分法所屬現(xiàn)代詞，指的是數(shù)學(xué)領(lǐng)域的概念，經(jīng)常用于計(jì)算機(jī)中的查找過(guò)程中。數(shù)學(xué)方面牛頓二分法 一般地，對(duì)于函數(shù)f(x),如果存在實(shí)數(shù)c,當(dāng)x=c時(shí)，若f(c)=0,那么把x=c叫做函數(shù)f(x)的零點(diǎn)。解方程即要求f(x)的所有零點(diǎn)。假定f(x)在區(qū)間（x，y）上連續(xù)先找到a、b屬于區(qū)間（x，y），使f(a)，f(b)異號(hào)，說(shuō)明在區(qū)間(a,b)內(nèi)一定有零點(diǎn)，然后求f[(a+b)/2], 現(xiàn)在假設(shè)f(a)<0,f(b)>0,a。

二分法_二分法 -簡(jiǎn)介

二分法_二分法 -使用示例：

二分法_二分法 -證明方法

二分法（dichotomie）即一分為二的方法.設(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)

二分法_二分法 -求法

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

1確定區(qū)間[a,b],驗(yàn)證f(a)?f(b)<0,給定精確度ξ.

2求區(qū)間(a,b)的中點(diǎn)c.

3計(jì)算f(c).

(1)若f(c)=0,則c就是函數(shù)的零點(diǎn);

(2)若f(a)?f(c)<0,則令b=c;

(3)若f(c)?f(b)<0,則令a=c.

(4)判斷是否達(dá)到精確度ξ:即若|a-b|<ξ,則得到零點(diǎn)近似值a(或b),否則重復(fù)2-4.

二分法_二分法 -計(jì)算機(jī)應(yīng)用

由于計(jì)算過(guò)程的具體運(yùn)算復(fù)雜，但每一步的方式相同，所以可通過(guò)編寫程序來(lái)運(yùn)算。

Java語(yǔ)言

publicintbinarySearch(int[]data,intaim){//以int數(shù)組為例，aim為需要查找的數(shù)

intstart=0;

intend=data.length-1;

intmid=(start+end)/2;//a

while(data[mid]!=aim&&end>start){//如果data[mid]等于aim則死循環(huán)，所以排除

if(data[mid]>aim){

end=mid-1;

}elseif(data[mid]<aim){

start=mid+1;

}

mid=(start+end)/2;//b，注意a，b

}

return(data[mid]!=aim)?-1:mid;//返回結(jié)果

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//針對(duì)已經(jīng)排序好的數(shù)組進(jìn)行查找（對(duì)上面代碼進(jìn)行的改進(jìn)）
publicstaticbooleanbinarySearch(int[]array,inttarget){
intleft=0;
intright=array.length-1;
intmid=(left+right)/2;
while(array[mid]!=target&&right>left){
if(array[mid]>target){
right=mid+1;
}
elseif(array[mid]<target){
left=mid+1;
}
mid=(left+right)/2;
//判斷在縮小范圍后，新的left或者right是否會(huì)將target排除
if(array[right]<target){
break;//若縮小后right比target小，即target不在數(shù)組中
}
elseif(array[left]>target){
break;//若縮小后left比target大，即target不在數(shù)組中
}
}
return(array[mid]==target);
}

C語(yǔ)言

方程式為：f(x)=0，示例中f(x)=1+x-x^3

使用示例：

inputabe:121e-5

solution:1.32472

源碼如下：

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<assert.h>

doublef(doublex)

{

return1+x-x*x*x;

}

intmain()

{

doublea=0,b=0,e=1e-5;

printf("inputabe:");

scanf("%lf%lf%lf",&a,&b,&e);

e=fabs(e);

if(fabs(f(a))<=e)

{

printf("solution:%lgn",a);

}

elseif(fabs(f(b))<=e)

{

printf("solution:%lgn",b);

}

elseif(f(a)*f(b)>0)

{

printf("f(%lg)*f(%lg)>0!need<=0!n",a,b);

}

else

{

while(fabs(b-a)>e)

{

doublec=(a+b)/2.0;

if(f(a)*f(c)<0)

b=c;

else

a=c;

}

printf("solution:%lgn",(a+b)/2.0);

}

return0;

}

C++語(yǔ)言

[類C編寫].

|f(x)|<10^-5f(x)=2x^3-4x^2+3x-6

#include"iostream"

#include"stdio.h"

#include"math.h"

#definenull0

doublefx(double);//f(x)函數(shù)

voidmain()

{

doublexa(null),xb(null),xc(null);

do

{

printf("請(qǐng)輸入一個(gè)范圍x0x1：");

std::cin>>xa>>xb;//輸入xaxb的值

printf("%f%f",xa,xb);

}

while(fx(xa)*fx(xb)>=0);//判斷輸入范圍內(nèi)是否包含函數(shù)值0

do

{

if(fx((xc=(xa+xb)/2))*fx(xb)<0)//二分法判斷函數(shù)值包含0的X取值區(qū)間

{

xa=xc;

}

else

{

xb=xc;

}

}

while(fx(xc)>pow(10.0,-5)||fx(xc)<-1*pow(10.0,-5));//判斷x根是否在接近函數(shù)值0的精確范圍內(nèi)

printf("n得數(shù)為：%f",xc);

}

doublefx(doublex)

{

return(2.0*pow(x,3)-4.0*pow(x,2)+3*x-6.0);

}

C++語(yǔ)言中的二分查找法

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

基本思想：假設(shè)數(shù)據(jù)是按升序排序的，對(duì)于給定值x，從序列的中間位置開始比較，如果當(dāng)前位置值等于x，則查找成功；若x小于當(dāng)前位置值，則在數(shù)列的前半段中查找；若x大于當(dāng)前位置值則在數(shù)列的后半段中繼續(xù)查找

，直到找到為止。

假如有一組數(shù)為3，12，24，36，55，68，75，88要查給定的值24.可設(shè)三個(gè)變量front，mid，end分別指向數(shù)據(jù)的上界，中間和下界，mid=（front+end）/2.

1.開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因?yàn)閙id>x，故應(yīng)在前半段中查找。

2.令新的end=mid-1=2，而front=0不變，則新的mid=1。此時(shí)x>mid，故確定應(yīng)在后半段中查找。

3.令新的front=mid+1=2，而end=2不變，則新的mid=2，此時(shí)a[mid]=x，查找成功。

如果要查找的數(shù)不是數(shù)列中的數(shù)，例如x=25，當(dāng)?shù)谌闻袛鄷r(shí)，x>a[mid]，按以上規(guī)律，令front=mid+1，即front=3，出現(xiàn)front>end的情況，表示查找不成功。

例：在有序的有N個(gè)元素的數(shù)組中查找用戶輸進(jìn)去的數(shù)據(jù)x。

算法如下：

1.確定查找范圍front=0，end=N-1，計(jì)算中項(xiàng)mid（front+end）/2。

2.若a[mid]=x或front>=end,則結(jié)束查找；否則，向下繼續(xù)。

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

代碼：

#include<iostream>

#defineN10

usingnamespacestd;

intmain()

{

inta[N],front,end,mid,x,i;

cout<<"請(qǐng)輸入已排好序的a數(shù)組元素:"<<endl;

for(i=0;i<N;i++)

cin>>a[i];

cout<<"請(qǐng)輸入待查找的數(shù)x:"<<endl;

cin>>x;

front=0;

end=N-1;

mid=(front+end)/2;

while(front<end&&a[mid]!=x)

{

if(a[mid]<x)front=mid+1;

if(a[mid]>x)end=mid-1;

mid=front+(end-front)/2;

}

if(a[mid]!=x)

cout<<"沒(méi)找到！"<<endl;

else

cout<<"找到了！在第"<<mid+1<<"項(xiàng)里。"<<endl;

return0;

}

MATLAB語(yǔ)言

快速排序偽代碼（非隨機(jī)）

快速排序偽代碼（隨機(jī)）

遞歸快排1

遞歸快排2

遞歸快排3

TNTA=arrayofinteger;

var

A:TNTA;

procedureQuicSort(varArr:TNTA;AStart,AEnd:Integer);

var

I,J,Sign:integer;

procedureSwitch(A,B:Integer);

var

Tmp:Integer;

begin

Tmp:=Arr[A];

Arr[A]:=Arr[B];

Arr[B]:=Tmp;

end;

begin

ifAEnd<=AStartthen

Exit;

Sign:=(AStart+AEnd)div2;

{Switchvalue}

Switch(Sign,AEnd);

{Starttosort}

J:=AStart;

forI:=AStarttoAEnd-1do

begin

if(Arr[I]<Arr[AEnd]){and(I<>J)}then

begin

Switch(J,I);

Inc(J);

end;

end;

Switch(J,AENd);

QuicSort(Arr,AStart,J);

QuicSort(Arr,J+1,AEnd);

end;

procedureTForm1.btn1Click(Sender:TObject);

const

LEN=10000;

var

I:Integer;

Start:Cardinal;

begin

SetLength(A,LEN);

Randomize;

forI:=Low(A)toHigh(A)do

A[I]:=Random(LEN*10);

Start:=GetTickCount;

QuicSort(A,Low(A),High(A));

ShowMessageFmt('%dlargequicksorttaketime:%d',[LEN,GetTickCount-Start]);

end;

Pascal，非遞歸快排1

非遞歸快排2

二分法_二分法 -實(shí)戰(zhàn)

二分法_二分法 -經(jīng)濟(jì)學(xué)方面

二分法_二分法 -哲學(xué)方面

二分法_二分法 -一般使用方面

愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/8103420103/92537.html