二分法

二分法所属现代词，指的是数学领域的概念，经常用于计算机中的查找来自过程中。

• 中文名 二分法
• 外文名 Dichotomy
• 类型 数学
• 性质 指的是数学领域的概念，经常用于计算机中的查找过程中

基本思想

　　尼乎四练打钟误后神缺方把函数f(x)的零点所在的区间[a，b](满足f(a）●f(b）<0)“一分为二”，得到[a，m]和[m，b]。根据“f(a除担么转短略伤局文也)●f(m)<0”是否成立，取出零点所在的区间[a，m]或[m，b]，仍记为[来自a，b]。所对得的区间[之包美沉保口a，b]重复上述步骤氢，直到包含零点的区间[a，b]“足够小”，则[a，b]内的数可以作为方程的近似解。

证明方法

　　360百科二分法(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语言

　　public int binarySearch(int[] data,int aim){//以int数组为例，aim为需要查找的数

　　int start = 0;

　　int end = data.length-1;

　　int mid = (start+end)/2;//a

　　while(data[mid]!=aim&&end>start){//如果data[mid]等于aim则死循环，所以排除

　　if(data[mid]>aim){

　　end = mid-1;

　　}else if(data[mid]<aim){

　　start = mid+1;

　　}

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

　　}

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

　　}

　　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: %lg\n", a);

　　}

　　else if (fabs(f(b)) <= e)

　　{

　　printf("solution: %lg\n", 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: %lg\n", (a+b)/2.0);

　　}

　　return 0;

　　}

　　C++语言

　　[类C编写].

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

　　#include"iostream"

　　#include"stdio.h"

　　#include"math.h"

　　#define null 0

　　double fx(double); //f(x)函数

　　void main()

　　{

　　double xa(null),xb(null),xc(null);

　　do

　　{

　　printf("请输入一个范围x0 x1:");

　　std::cin>>xa>>xb; //输入xa xb的值

　　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);

　　}

　　double fx(double x)

　　{

　　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>

　　#define N 10

　　using namespace std;

　　int main()

　　{

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

　　cout<<"请输入已排好序的a数组元素:"<<endl;

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

　　cin>>a;

　　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;

　　return 0;

　　}

　　MATLAB语言

　　function y=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)

　　while abs(fc)>=ε; %判断f(c)是否为零点

　　if fa*fc>=0; %判断左侧区间是否有根

　　fa=fc;

　　a=c;

　　else fb=fc;

　　b=c;

　　end

　　c=(a+b)/2;

　　fc=f(c);

　　i=i+1;

　　end

　　fprintf('\n%s%.6f\t%s%d','c,'迭代次数i=',i) %计算结果输出

　　快速排序伪代码(非随机)

　　下面的过程实现快速排序:

　　QUICKSORT(A，p，r)

　　1 ifp<r

　　2 thenq ← PARTITION(A，p，r)

　　3 QUICKSORT(A，p，q-1)

　　4 QUICKSORT(A，q+1，r)

　　为排序一个完整的数组A，最初的调用是QUICKSORT(A，1，length[A])。

　　快速排序算法的关键是PARTITION过程，它对子数组A[p..r]进行就地重排:

　　PARTITION(A，p，r)

　　1 x ← A[r]

　　2 i ← p-1

　　3 forj ← ptor-1

　　4 do ifA[j]≤x

　　5 theni ← i+1

　　6 exchange A[i]←→A[j]

　　7 exchange A[i+1]←→A[r]

　　8 returni+1

　　快速排序伪代码(随机)

　　对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中，我们在真正进行划分之前实现交换:

　　(其中PARTITION过程同快速排序伪代码(非随机))

　　RANDOMIZED-PARTITION(A，p，r)

　　1 i ← RANDOM(p，r)

　　2 exchange A[r]←→A[i]

　　3 return PARTITION(A，p，r)

　　新的快速排序过程不再调用PARTITION，而是调用RANDOMIZED-PARTITION。

　　RANDOMIZED-QUICKSORT(A，p，r)

　　1 ifp<r

　　2 thenq ← RANDOMIZED-PARTITION(A，p，r)

　　3 RANDOMIZED-QUICKSORT(A，p，q-1)

　　4 RANDOMIZED-QUICKSORT(A，q+1，r)

　　Pascal，递归快排1

　　procedure work(l,r: longint);

　　var i,j,tmp: longint;

　　begin

　　if l<r then begin

　　i:=l;j:=r;tmp:=stone;

　　while i<j do

　　begin

　　while (i<j)and(tmp<stone[j])do dec(j);

　　if(i<j) then

　　begin

　　stone:=stone[j];

　　inc(i);

　　end;

　　while (i<j)and(tmp>stone)do inc(i);

　　if i<j then

　　begin

　　stone[j]:=stone;

　　dec(j);

　　end;

　　end;

　　stone:=tmp;

　　work(l,i-1);

　　work(i+1,r);

　　end;

　　end;//本段程序中stone是要排序的数组，从小到大排序，stone数组为longint(长整型)类型。在主程序中的调用命令为"work(1,n);"不含引号。表示将stone数组中的1到n号元素进行排序。

　　Pascal，递归快排2

　　Program quiksort;

　　//快速排序法

　　const max=100;

　　var n:integer;

　　a:array[1..max] of longint;

　　procedure sort(l,r: longint);

　　var i,j,x,y: longint;

　　begin

　　i:=l; j:=r; x:=a[(l+r) div 2];

　　repeat

　　while a<x do inc(i);

　　while x<a[j] do dec(j);

　　if i<=j then

　　begin

　　y:=a; a:=a[j]; a[j]:=y;

　　inc(i); dec(j);

　　end;

　　until i>j;

　　if l<j then sort(l,j);

　　if i<r then sort(i,r);

　　end;

　　begin

　　//生成数组;

　　randomize;

　　for n:=1 to max do

　　begin

　　a[n]:=random(1000);

　　write(a[n]:5);

　　end;

　　writeln;

　　//排序

　　sort(1,max);

　　//输出

　　for n:=1 to max do write(a[n]:5);writeln;

　　end.

　　Delphi 递归快排3

　　type

　　TNTA=array of integer;

　　var

　　A:TNTA;

　　procedure QuicSort(var Arr:TNTA;AStart,AEnd:Integer);

　　var

　　I,J,Sign:integer;

　　procedure Switch(A,B:Integer);

　　var

　　Tmp:Integer;

　　begin

　　Tmp:=Arr[A];

　　Arr[A]:=Arr;

　　Arr:=Tmp;

　　end;

　　begin

　　if AEnd<=AStart then

　　Exit;

　　Sign:=(AStart+AEnd)div 2;

　　{Switch value}

　　Switch(Sign,AEnd);

　　{Start to sort}

　　J:=AStart;

　　for I := AStart to AEnd-1 do

　　begin

　　if (Arr<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;

　　procedure TForm1.btn1Click(Sender: TObject);

　　const

　　LEN=10000;

　　var

　　I: Integer;

　　Start:Cardinal;

　　begin

　　SetLength(A,LEN);

　　Randomize;

　　for I := Low(A) to High(A) do

　　A:=Random(LEN*10);

　　Start:=GetTickCount;

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

　　ShowMessageFmt('%d large quick sort take time:%d',[LEN,GetTickCount-Start]);

　　end;

　　Pascal，非递归快排1

　　var

　　s:packed array[0..100,1..7]of longint;

　　t:boolean;

　　i,j,k,p,l,m,n,r,x,ii,jj,o:longint;

　　a:packed array[1..200000]of longint;

　　function check:boolean;

　　begin

　　if i>2 then exit(false);

　　case i of

　　1:if (s[k,3]<s[k,2]) then exit(true);

　　2:if s[k,1]<s[k,4] then exit(true);

　　end;

　　exit(false);

　　end;

　　procedure qs; //非递归快速排序

　　begin

　　k:=1;

　　t:=true;

　　s[k,1]:=1;

　　s[k,2]:=n;

　　s[k,3]:=1;

　　while k>0 do

　　begin

　　r:=s[k,2];

　　l:=s[k,1];

　　ii:=s[k,3];

　　jj:=s[k,4];

　　if t then

　　if (r-l>30) then

　　begin

　　x:=a[(r-l+1)shr 1 +l];

　　ii:=s[k,1];jj:=s[k,2];

　　repeat

　　while a[ii]<x do inc(ii);

　　while a[jj]>x do dec(jj);

　　if ii<=jj then

　　begin

　　m:=a[ii];

　　a[ii]:=a[jj];

　　a[jj]:=m;

　　inc(ii);dec(jj);

　　end;

　　until ii>jj;

　　s[k,3]:=ii;

　　s[k,4]:=jj;

　　end

　　else begin

　　for ii:=l to r do

　　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;

　　if t then

　　for i:=1 to 3 do

　　if check then break;

　　if not t then

　　begin

　　i:=s[k,5];

　　repeat

　　inc(i);

　　until (i>2)or check;

　　end;

　　if i>2 then begin t:=false; dec(k);end

　　else t:=true;

　　if t then

　　begin

　　s[k,5]:=i;

　　inc(k);

　　case i of

　　1:begin s[k,1]:=s[k-1,3];s[k,2]:=s[k-1,2];end;

　　2:begin s[k,1]:=s[k-1,1];s[k,2]:=s[k-1,4];end;

　　end;

　　end;

　　end;

　　end;

　　begin

　　readln(n);

　　for i:=1 to n do read(a);

　　k:=1;

　　qs;

　　for i:=1 to n do //输出

　　write(a,' ');

　　writeln;

　　end.

　　经测试，非递归快排比递归快排快。

　　Pascal，非递归快排2

　　//此段快排使用l队列储存待处理范围

　　var

　　a:Array[1..100000] of longint;

　　l:Array[1..100000,1..2] of longint;

　　n,i:longint;

　　procedure fs;//非递归快排

　　var

　　s,e,k,j,ms,m:longint;

　　begin

　　s:=1;e:=1;l[1,1]:=1;l[1,2]:=n;

　　while s<=e do

　　begin

　　k:=l[s,1];j:=l[s,2];m:=random(j-k+1)+k;

　　ms:=a[m];a[m]:=a[k];

　　while k<j do

　　begin

　　while (k<j)and(a[j]>ms) do dec(j);

　　if k<j then begin a[k]:=a[j];inc(k);end;

　　while (k<j)and(a[k]<ms) do inc(k);

　　if k<j then begin a[j]:=a[k];dec(j);end;

　　end;

　　a[k]:=ms;

　　if l[s,1]<k-1 then begin inc(e);l[e,1]:=l[s,1];l[e,2]:=k-1;end;

　　if j+1<l[s,2] then begin inc(e);l[e,1]:=j+1;l[e,2]:=l[s,2];end;

　　inc(s);

　　end;

　　end;

　　begin

　　randomize;

　　read(n);

　　for i:=1 to n do read(a);

　　fs;

　　for i:=1 to n do write(a,' ');

　　end.

　　实战

　　Problem:大整数开方 NOIP2011普及组初赛完善程序第二题

　　题目描述

　　输入一个正整数n(1<n<10^100)，试用二分法计算它的平方根的整数部分。

　　代码

　　Const

　　SIZE = 200;

　　Type

　　hugeint = Record

　　len : Integer;

　　num : Array[1..SIZE] Of Integer;

　　End;

　　//len表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推

　　Var

　　s : String;

　　i : Integer;

　　target, left, middle, right : hugeint;

　　Function times(a, b : hugeint) : hugeint;

　　// 计算大整数 a 和 b 的乘积

　　Var

　　i, j : Integer;

　　ans : hugeint;

　　Begin

　　FillChar(ans, SizeOf(ans), 0);

　　For i := 1 To a.len Do

　　For j := 1 To b.len Do

　　ans.num[i + j - 1] := ans.num[i + j - 1] + a.num * b.num[j];

　　For i := 1 To a.len + b.len Do

　　Begin

　　ans.num[i + 1] := ans.num[i + 1] + ans.num DIV 10;

　　ans.num := ans.num mod 10;

　　If ans.num[a.len + b.len] > 0

　　Then ans.len := a.len + b.len

　　Else ans.len := a.len + b.len - 1;

　　End;

　　times := ans;

　　End;

　　Function add(a, b : hugeint) : hugeint;

　　// 计算大整数 a 和 b 的和

　　Var

　　i : Integer;

　　ans : hugeint;

　　Begin

　　FillChar(ans.num, SizeOf(ans.num), 0);

　　If a.len > b.len

　　Then ans.len := a.len

　　Else ans.len := b.len;

　　For i := 1 To ans.len Do

　　Begin

　　ans.num :=ans.num + a.num + b.num;

　　ans.num[i + 1] := ans.num[i + 1] + ans.num DIV 10;

　　ans.num := ans.num MOD 10;

　　End;

　　If ans.num[ans.len + 1] > 0

　　Then Inc(ans.len);

　　add := ans;

　　End;

　　Function average(a, b : hugeint) : hugeint;

　　// 计算大整数 a 和 b 的平均数的整数部分

　　Var

　　i : Integer;

　　ans : hugeint;

　　Begin

　　ans := add(a, b);

　　For i := ans.len DownTo 2 Do

　　Begin

　　ans.num[i - 1] := ans.num[i - 1] + (ans.num mod 2) * 10;

　　ans.num := ans.num DIV 2;

　　End;

　　ans.num[1] := ans.num[1] DIV 2;

　　If ans.num[ans.len] = 0

　　Then Dec(ans.len);

　　average := ans;

　　End;

　　Function plustwo(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 >= 10) Do

　　Begin

　　ans.num[i + 1] := ans.num[i + 1] + ans.num DIV 10;

　　ans.num := ans.num MOD 10;

　　Inc(i);

　　End;

　　If ans.num[ans.len + 1] > 0

　　Then inc(ans.len);

　　plustwo := ans;

　　End;

　　Function over(a, b : hugeint) : Boolean;

　　// 若大整数 a > b 则返回 1, 否则返回 0

　　Var

　　i : Integer;

　　Begin

　　If (a.len<b.len) Then

　　Begin

　　over := FALSE;

　　Exit;

　　End;

　　If a.len > b.len Then

　　Begin

　　over := TRUE;

　　Exit;

　　End;

　　For i := a.len DownTo 1 Do

　　Begin

　　If a.num < b.num Then

　　Begin

　　over := FALSE;

　　Exit;

　　End;

　　If a.num > b.num Then

　　Begin

　　over := TRUE;

　　Exit;

　　End;

　　End;

　　over := FALSE;

　　End;

　　Begin

　　Readln(s);

　　FillChar(target.num, SizeOf(target.num), 0);

　　target.len := Length(s);

　　For i := 1 To target.len Do

　　target.num := 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);

　　If over(times(middle, middle), target)

　　Then right := middle

　　Else left := middle;

　　Until over(plustwo(left), right);

　　For i := left.len DownTo 1 Do

　　Write(left.num);

　　Writeln;

　　End.