二分法[數學領域術語]

對於區間[a，b]上連續不斷且f（a）·f（b）

定義

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

典型算法

算法：當數據量很大適宜採用該方法。採用二分法查找時，數據需是排好序的。

基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，

如果當前位置arr[k]值等於key，則查找成功；

若key小於當前位置值arr[k]，則在數列的前半段中查找,arr[low,mid-1]；

若key大於當前位置值arr[k]，則在數列的後半段中繼續查找arr[mid+1,high]，

直到找到為止,時間複雜度:O(log(n)) 。

求法

給定精確度ξ,用二分法求函式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

源碼如下：

C++語言

[類C編寫].

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

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

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　 if p< r

2　 then q ← 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　 for j ← p to r-1

4　 do if A[ j]≤ x

5　 then i ← i+1

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

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

8　 return i+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　 if p< r

2　 then q ← 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[i];

while i<j do

begin

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

if(i<j) then

begin

stone[i]:=stone[j];

inc(i);

end;

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

if i<j then

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

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[i]<x do inc(i);

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

if i<=j then

begin

y:=a[i]; a[i]:=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[B];

Arr[B]:=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[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;

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[I]:=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[i]);

k:=1;

qs;

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

write(a[i],' ');

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[i]);

fs;

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

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[i] * b.num[j];
For i := 1 To a.len + b.len Do
Begin
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10;
ans.num[i] := ans.num[i] 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[i] :=ans.num[i] + a.num[i] + b.num[i];
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10;
ans.num[i] := ans.num[i] 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[i] mod 2) * 10;
ans.num[i] := ans.num[i] 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[i] >= 10) Do
Begin
ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10;
ans.num[i] := ans.num[i] 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[i] < b.num[i] Then
Begin
over := FALSE;
Exit;
End;
If a.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);
For i := 1 To target.len Do
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);
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[i]);
Writeln;
End.