二分法

    2.  
  2. 主页
  3.  / 
  4. 文档
  5.  / 
  6. 二分法
  7.  / 
  8. 二分法实战

二分法实战

由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。
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;//返回结果
}
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
使用示例：
input a b e: 1 2 1e-5
solution: 1.32472
源码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cmath>
using namespace std;
double f(double x);
const double Accu = pow(10.0, -5.0); // define accuracy
int main()
{
double a, b, c;
a = b = c = 0;
do
{
cout << "Enter a range: ";
cin >> a >> b;
} while (!cin || f(a) * f(b) >= 0); // bad input or f(a) * f(b) >= 0
do
{
c = (a + b) / 2.0; // c is the average number of a and b
if (f(a) * f(c) < 0)
b = c;
else if (f(b) * f(c) < 0)
a = c;
else
break;
} while ( abs(f(c)) > Accu); // if deviation is smaller than pow(10.0, -5.0)
cout << "Solution: " << c;
return 0;
}
double f(double x)
{
    return (2 * x * x * x - 4 * x * x + 3 * x - 6); // or 2 * pow(x, 3.0) - 4 * pow(x, 2.0) + 3 * x - 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　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[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.

去年今日运营文章

  1. 2022:  运营人必须要懂的9大运营模型，面试、沙龙、写工作总结都用得到(0)
  2. 2022:  2022抖音年轻人观察报告(0)
  3. 2022:  职场：解决问题七步法(0)
  4. 2022:  斜杠青年副业月入过万，别搞笑了(0)
  5. 2021:  小红书怎么推广？3大关键赋能产品价值，助力品牌增长！(0)
标签
这篇文章对您有用吗？ 是 否

发表回复

登录后才能评论