爱华网二分法所属现代词，指的是数学领域的概念，经常用于计算机中的查找过程中。数学方面牛顿二分法 一般地，对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。假定f(x)在区间（x，y）上连续先找到a、b属于区间（x，y），使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f[(a+b)/2], 现在假设f(a)<0,f(b)>0,a。
二分法_二分法 -简介
一般地，对于函数f(x),如果存在实数c,当x=c是f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。
先找到a、b，使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f【(a+b)/2】,
现在假设f(a)<0,f(b)>0,a<b
如果f【(a+b)/2】=0，该点就是零点，
如果f【(a+b)/2】<0,则在区间（(a+b)/2，b)内有零点，按上述方法在求该区间中点的函数值，这样就可以不断接近零点
如果f【(a+b)/2】>0，同上
通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。
由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。
例:(C语言)
方程式为：f(x) = 0，示例中f(x) = 1+x-x^3
二分法_二分法 -使用示例：
input a b e: 1 2 1e-5
solution: 1.32472
源码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
double f(double x)
{
return 1+x-x*x*x;
}
int main()
{
double a = 0, b = 0, e = 1e-5;
printf("input a b e: ");
scanf("%lf%lf%lf", &a, &b, &e);
e = fabs(e);
if (fabs(f(a)) <= e)
{
printf("solution: %lgn", a);
}
else if (fabs(f(b)) <= e)
{
printf("solution: %lgn", b);
}
else if (f(a)*f(b) > 0)
{
printf("f(%lg)*f(%lg) > 0 ! need <= 0 !n", a, b);
}
else
{
while (fabs(b-a) > e)
{
double c = (a+b)/2.0;
if (f(a)* f ( c ) < 0)
b = c;
else
a = c;
}
printf("solution: %lgn", (a+b)/2.0);
}
return 0;
}
二分法_二分法 -证明方法
二分法（dichotomie）即一分为二的方法.设[a，b]为R的紧区间.逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点
二分法_二分法 -求法
给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下:
1确定区间[a,b],验证f(a)・f(b)<0,给定精确度ξ.
2求区间(a,b)的中点c.
3计算f(c).
(1)若f(c)=0,则c就是函数的零点;
(2)若f(a)・f(c)<0,则令b=c;
(3)若f(c)・f(b)<0,则令a=c.
(4)判断是否达到精确度ξ:即若|a-b|<ξ,则得到零点近似值a(或b),否则重复2-4.
二分法_二分法 -计算机应用
由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。
Java语言
publicintbinarySearch(int[]data,intaim){//以int数组为例，aim为需要查找的数
intstart=0;
intend=data.length-1;
intmid=(start+end)/2;//a
while(data[mid]!=aim&&end>start){//如果data[mid]等于aim则死循环，所以排除
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;//返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//针对已经排序好的数组进行查找（对上面代码进行的改进）
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是否会将target排除
if(array[right]<target){
break;//若缩小后right比target小，即target不在数组中
}
elseif(array[left]>target){
break;//若缩小后left比target大，即target不在数组中
}
}
return(array[mid]==target);
}
C语言
方程式为：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++语言
[类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)函数
voidmain()
{
doublexa(null),xb(null),xc(null);
do
{
printf("请输入一个范围x0x1：");
std::cin>>xa>>xb;//输入xaxb的值
printf("%f%f",xa,xb);
}
while(fx(xa)*fx(xb)>=0);//判断输入范围内是否包含函数值0
do
{
if(fx((xc=(xa+xb)/2))*fx(xb)<0)//二分法判断函数值包含0的X取值区间
{
xa=xc;
}
else
{
xb=xc;
}
}
while(fx(xc)>pow(10.0,-5)||fx(xc)<-1*pow(10.0,-5));//判断x根是否在接近函数值0的精确范围内
printf("n得数为：%f",xc);
}
doublefx(doublex)
{
return(2.0*pow(x,3)-4.0*pow(x,2)+3*x-6.0);
}
C++语言中的二分查找法
算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。
基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找
，直到找到为止。
假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.
1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。
2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。
3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。
如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。
例：在有序的有N个元素的数组中查找用户输进去的数据x。
算法如下：
1.确定查找范围front=0，end=N-1，计算中项mid（front+end）/2。
2.若a[mid]=x或front>=end,则结束查找；否则，向下继续。
3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。
代码：
#include<iostream>
#defineN10
usingnamespacestd;
intmain()
{
inta[N],front,end,mid,x,i;
cout<<"请输入已排好序的a数组元素:"<<endl;
for(i=0;i<N;i++)
cin>>a[i];
cout<<"请输入待查找的数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<<"没找到！"<<endl;
else
cout<<"找到了！在第"<<mid+1<<"项里。"<<endl;
return0;
}
MATLAB语言
functiony=f(x)
y=f(x);%函数f(t)的表达式
i=0;%二分次数记数
a=a;%求根区间左端
b=b;%求根区间右端
fa=f(a);%计算f(a)的值
fb=f(b);%计算f(b)的值
c=(a+b)/2;%计算区间中点
fc=f(c);%计算区间中点f(c)
whileabs(fc)>=ε;%判断f(c)是否为零点
iffa*fc>=0;%判断左侧区间是否有根
fa=fc;
a=c;
elsefb=fc;
b=c;
end
c=(a+b)/2;
fc=f(c);
i=i+1;
end
fprintf('n%s%.6ft%s%d','c,'迭代次数i=',i)%计算结果输出
快速排序伪代码（非随机）
下面的过程实现快速排序：
QUICKSORT(A，p，r)
1ifp<r
2thenq←PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
为排序一个完整的数组A，最初的调用是QUICKSORT(A，1，length[A])。
快速排序算法的关键是PARTITION过程，它对子数组A[p..r]进行就地重排：
PARTITION(A，p，r)
1x←A[r]
2i←p-1
3forj←ptor-1
4doifA[j]≤x
5theni←i+1
6exchangeA[i]←→A[j]
7exchangeA[i+1]←→A[r]
8returni+1
快速排序伪代码（随机）
对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中，我们在真正进行划分之前实现交换：（其中PARTITION过程同快速排序伪代码（非随机））
RANDOMIZED-PARTITION(A，p，r)
1i←RANDOM(p，r)
2exchangeA[r]←→A[i]
3returnPARTITION(A，p，r)
新的快速排序过程不再调用PARTITION，而是调用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1ifp<r
2thenq←RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r)
Pascal，
递归快排1
procedurework(l,r:longint);
vari,j,tmp:longint;
begin
ifl<rthenbegin
i:=l;j:=r;tmp:=stone[i];
whilei<jdo
begin
while(i<j)and(tmp<stone[j])dodec(j);
if(i<j)then
begin
stone[i]:=stone[j];
inc(i);
end;
while(i<j)and(tmp>stone[i])doinc(i);
ifi<jthen
begin
stone[j]:=stone[i];
dec(j);
end;
end;
stone[i]:=tmp;
work(l,i-1);
work(i+1,r);
end;
end;//本段程序中stone是要排序的数组，从小到大排序，stone数组为longint（长整型）类型。在主程序中的调用命令为“work(1,n);”不含引号。表示将stone数组中的1到n号元素进行排序。
Pascal，
递归快排2
Programquiksort;
//快速排序法
constmax=100;
varn:integer;
a:array[1..max]oflongint;
proceduresort(l,r:longint);
vari,j,x,y:longint;
begin
i:=l;j:=r;x:=a[(l+r)div2];
repeat
whilea[i]<xdoinc(i);
whilex<a[j]dodec(j);
ifi<=jthen
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
untili>j;
ifl<jthensort(l,j);
ifi<rthensort(i,r);
end;
begin
//生成数组;
randomize;
forn:=1tomaxdo
begin
a[n]:=random(1000);
write(a[n]:5);
end;
writeln;
//排序
sort(1,max);
//输出
forn:=1tomaxdowrite(a[n]:5);writeln;
end.
Delphi
递归快排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
var
s:packedarray[0..100,1..7]oflongint;
t:boolean;
i,j,k,p,l,m,n,r,x,ii,jj,o:longint;
a:packedarray[1..200000]oflongint;
functioncheck:boolean;
begin
ifi>2thenexit(false);
caseiof
1:if(s[k,3]<s[k,2])thenexit(true);
2:ifs[k,1]<s[k,4]thenexit(true);
end;
exit(false);
end;
procedureqs;/非递归快速排序
begin
k:=1;
t:=true;
s[k,1]:=1;
s[k,2]:=n;
s[k,3]:=1;
whilek>0do
begin
r:=s[k,2];
l:=s[k,1];
ii:=s[k,3];
jj:=s[k,4];
iftthen
if(r-l>30)then
begin
x:=a[(r-l+1)shr1+l];
ii:=s[k,1];jj:=s[k,2];
repeat
whilea[ii]<xdoinc(ii);
whilea[jj]>xdodec(jj);
ifii<=jjthen
begin
m:=a[ii];
a[ii]:=a[jj];
a[jj]:=m;
inc(ii);dec(jj);
end;
untilii>jj;
s[k,3]:=ii;
s[k,4]:=jj;
end
elsebegin
forii:=ltordo
begin
m:=a[ii];jj:=ii-1;
while(m<a[jj])and(jj>0)do
begin
a[jj+1]:=a[jj];
dec(jj);
end;
a[jj+1]:=m;
end;
t:=false;dec(k);
end;
iftthen
fori:=1to3do
ifcheckthenbreak;
ifnottthen
begin
i:=s[k,5];
repeat
inc(i);
until(i>2)orcheck;
end;
ifi>2thenbegint:=false;dec(k);end
elset:=true;
iftthen
begin
s[k,5]:=i;
inc(k);
caseiof
1:begins[k,1]:=s[k-1,3];s[k,2]:=s[k-1,2];end;
2:begins[k,1]:=s[k-1,1];s[k,2]:=s[k-1,4];end;
end;
end;
end;
end;
begin
readln(n);
fori:=1tondoread(a[i]);
k:=1;
qs;
fori:=1tondo//输出
write(a[i],'');
writeln;
end.
经测试，非递归快排比递归快排快。
Pascal，
非递归快排2
//此段快排使用l队列储存待处理范围
var
a:Array[1..100000]oflongint;
l:Array[1..100000,1..2]oflongint;
n,i:longint;
procedurefs;//非递归快排
var
s,e,k,j,ms,m:longint;
begin
s:=1;e:=1;l[1,1]:=1;l[1,2]:=n;
whiles<=edo
begin
k:=l[s,1];j:=l[s,2];m:=random(j-k+1)+k;
ms:=a[m];a[m]:=a[k];
whilek<jdo
begin
while(k<j)and(a[j]>ms)dodec(j);
ifk<jthenbegina[k]:=a[j];inc(k);end;
while(k<j)and(a[k]<ms)doinc(k);
ifk<jthenbegina[j]:=a[k];dec(j);end;
end;
a[k]:=ms;
ifl[s,1]<k-1thenbegininc(e);l[e,1]:=l[s,1];l[e,2]:=k-1;end;
ifj+1<l[s,2]thenbegininc(e);l[e,1]:=j+1;l[e,2]:=l[s,2];end;
inc(s);
end;
end;
begin
randomize;
read(n);
fori:=1tondoread(a[i]);
fs;
fori:=1tondowrite(a[i],'');
end.
二分法_二分法 -实战
Problem：大整数开方NOIP2011普及组初赛完善程序第二题
题目描述
输入一个正整数n(1<n<10^100)，试用二分法计算它的平方根的整数部分。
代码
Const
SIZE=200;
Type
hugeint=Record
len:Integer;
num:Array[1..SIZE]OfInteger;
End;
//len表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推
Var
s:String;
i:Integer;
target,left,middle,right:hugeint;
Functiontimes(a,b:hugeint):hugeint;
//计算大整数a和b的乘积
Var
i,j:Integer;
ans:hugeint;
Begin
FillChar(ans,SizeOf(ans),0);
Fori:=1Toa.lenDo
Forj:=1Tob.lenDo
ans.num[i+j-1]:=ans.num[i+j-1]+a.num[i]*b.num[j];
Fori:=1Toa.len+b.lenDo
Begin
ans.num[i+1]:=ans.num[i+1]+ans.num[i]DIV10;
ans.num[i]:=ans.num[i]mod10;
Ifans.num[a.len+b.len]>0
Thenans.len:=a.len+b.len
Elseans.len:=a.len+b.len-1;
End;
times:=ans;
End;
Functionadd(a,b:hugeint):hugeint;
//计算大整数a和b的和
Var
i:Integer;
ans:hugeint;
Begin
FillChar(ans.num,SizeOf(ans.num),0);
Ifa.len>b.len
Thenans.len:=a.len
Elseans.len:=b.len;
Fori:=1Toans.lenDo
Begin
ans.num[i]:=ans.num[i]+a.num[i]+b.num[i];
ans.num[i+1]:=ans.num[i+1]+ans.num[i]DIV10;
ans.num[i]:=ans.num[i]MOD10;
End;
Ifans.num[ans.len+1]>0
ThenInc(ans.len);
add:=ans;
End;
Functionaverage(a,b:hugeint):hugeint;
//计算大整数a和b的平均数的整数部分
Var
i:Integer;
ans:hugeint;
Begin
ans:=add(a,b);
Fori:=ans.lenDownTo2Do
Begin
ans.num[i-1]:=ans.num[i-1]+(ans.num[i]mod2)*10;
ans.num[i]:=ans.num[i]DIV2;
End;
ans.num[1]:=ans.num[1]DIV2;
Ifans.num[ans.len]=0
ThenDec(ans.len);
average:=ans;
End;
Functionplustwo(a:hugeint):hugeint;
//计算大整数a加2后的结果
Var
i:Integer;
ans:hugeint;
Begin
ans:=a;
ans.num[1]:=ans.num[1]+2;
i:=1;
While(i<=ans.len)AND(ans.num[i]>=10)Do
Begin
ans.num[i+1]:=ans.num[i+1]+ans.num[i]DIV10;
ans.num[i]:=ans.num[i]MOD10;
Inc(i);
End;
Ifans.num[ans.len+1]>0
Theninc(ans.len);
plustwo:=ans;
End;
Functionover(a,b:hugeint):Boolean;
//若大整数a>b则返回1,否则返回0
Var
i:Integer;
Begin
If(a.len<b.len)Then
Begin
over:=FALSE;
Exit;
End;
Ifa.len>b.lenThen
Begin
over:=TRUE;
Exit;
End;
Fori:=a.lenDownTo1Do
Begin
Ifa.num[i]<b.num[i]Then
Begin
over:=FALSE;
Exit;
End;
Ifa.num[i]>b.num[i]Then
Begin
over:=TRUE;
Exit;
End;
End;
over:=FALSE;
End;
Begin
Readln(s);
FillChar(target.num,SizeOf(target.num),0);
target.len:=Length(s);
Fori:=1Totarget.lenDo
target.num[i]:=Ord(s[target.len-i+1])-ord('0');
FillChar(left.num,SizeOf(left.num),0);
left.len:=1;
left.num[1]:=1;
right:=target;
Repeat
middle:=average(left,right);
Ifover(times(middle,middle),target)
Thenright:=middle
Elseleft:=middle;
Untilover(plustwo(left),right);
Fori:=left.lenDownTo1Do
Write(left.num[i]);
Writeln;
End.
二分法_二分法 -经济学方面
传统的经济学家把经济分为实物经济和货币经济两部分，其中，经济理论分析实际变量的决定，而货币理论分析价格的决定，两者之间并没有多大的关系，这就是所谓的二分法。
二分法_二分法 -哲学方面
又称二分说，爱利亚学派芝诺四大著名悖论之一证明运动是不可能的。其主要思路是：假设一个存在物经过空间而运动，为了穿越某个空间，就必须穿越这个空间的一半。为了穿越这一半，就必须穿越这一半的一半；以此类推，直至无穷。所以，运动是不可能的二分法_二分法 -一般使用方面
即将所有的事物根据其属性分成两种。错误的分类可能导致逻辑谬论，如：非黑即白，不是忠的就是奸的。这很明显忽略了中间状态的存在。正确的分类法应如：白-非白。
