「二分法java递归」二分法 Java

本篇文章给大家谈谈二分法java递归，以及二分法 Java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、二分法查找的java代码
• 2、二分法的计算机应用
• 3、写一个java程序,用二分法把6插入到数组[1,2,5,7,8,9,13]
• 4、用二分法查找（折半查找）java
• 5、Java二分法
• 6、二分法逻辑及实现

二分法查找的java代码

public class ef {

public static void main(String[] args) {

int[] a = { 4, 8, 12, 44, 69, 71, 98, 132 ,133};

int m = ef.ef(a, 0, a.length, 71);

if(m!=-1){

System.out.println(a[m]+"====="+m);

}

System.out.println("不存在该数字");

}

public static int ef(int[] a, int from, int to, int b) {

int midel = (from + to) / 2;

if ((to - from) = 1 b != a[midel]) {

return -1;

}

if (b a[midel]) {

return ef(a, midel, to, b);

} else if (b a[midel]) {

return ef(a, from, midel, b);

} else {

return midel;

}

}

}

二分法的计算机应用

由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。

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]!=aimendstart){//如果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;//返回结果

} //针对已经排序好的数组进行查找（对上面代码进行的改进）publicstaticbooleanbinarySearch(int[]array,inttarget){intleft=0;intright=array.length-1;intmid=(left+right)/2;while(array[mid]!=targetrightleft){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

源码如下： #include stdio.h#include stdlib.h#include math.h#include assert.hdouble 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 cmathusing namespace std;double f(double x);const double Accu = pow(10.0, -5.0); // define accuracyint 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) = 0do{c = (a + b) / 2.0; // c is the average number of a and bif (f(a) * f(c)  0)b = c;else if (f(b) * f(c)  0)a = c;elsebreak;} while (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）。因为midx，故应在前半段中查找。

2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时xmid，故确定应在后半段中查找。

3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

如果要查找的数不是数列中的数，例如x=25，当第三次判断时，xa[mid]，按以上规律，令front=mid+1，即front=3，出现frontend的情况，表示查找不成功。

例：在有序的有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。

代码：

#includeiostream

#define N 10

using namespace std;

int main()

{

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

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

for(i=0;iN;i++)

cina[i];

cout请输入待查找的数x:endl;

cinx;

front=0;

end=N-1;

mid=(front+end)/2;

while(frontenda[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　ifpr

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　ifpr

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 lr then begin

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

while ij do

begin

while (ij)and(tmpstone[j])do dec(j);

if(ij) then

begin

stone[i]:=stone[j];

inc(i);

end;

while (ij)and(tmpstone[i])do inc(i);

if ij 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 xa[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 ij;

if lj then sort(l,j);

if ir 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 (IJ)} 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 i2 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 k0 do

begin

r:=s[k,2];

l:=s[k,1];

ii:=s[k,3];

jj:=s[k,4];

if t then

if (r-l30) 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 iijj;

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 (ma[jj])and(jj0) 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 (i2)or check;

end;

if i2 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 kj do

begin

while (kj)and(a[j]ms) do dec(j);

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

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

if kj 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+1l[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(1n10^100)，试用二分法计算它的平方根的整数部分。

代码

ConstSIZE = 200;

Typehugeint = Recordlen : Integer;num : Array[1..SIZE] Of Integer;End; //len表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推

Vars : String;i : Integer;target, left, middle, right : hugeint;

Function times(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的乘积Vari, j : Integer;ans : hugeint; BeginFillChar(ans, SizeOf(ans), 0);For i := 1 To a.len DoFor j := 1 To b.len Doans.num[i + j - 1] := ans.num[i + j - 1] + a.num[i] * b.num[j];For i := 1 To a.len + b.len DoBeginans.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] 0Then ans.len := a.len + b.lenElse ans.len := a.len + b.len - 1;End;times := ans; End;

Function add(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的和Vari : Integer;ans : hugeint; BeginFillChar(ans.num, SizeOf(ans.num), 0);If a.len b.lenThen ans.len := a.lenElse ans.len := b.len;For i := 1 To ans.len DoBeginans.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] 0Then Inc(ans.len);add := ans;End;

Function average(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的平均数的整数部分Vari : Integer;ans : hugeint; Beginans := add(a, b);For i := ans.len DownTo 2 DoBeginans.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] = 0Then Dec(ans.len);average := ans; End;

Function plustwo(a : hugeint) : hugeint; // 计算大整数 a 加 2 后的结果Vari : Integer;ans : hugeint; Beginans := a;ans.num[1] := ans.num[1] + 2;i := 1;While (i = ans.len) AND (ans.num[i] = 10) DoBeginans.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] 0Then inc(ans.len);plustwo := ans; End;

Function over(a, b : hugeint) : Boolean; // 若大整数 a b 则返回 1, 否则返回 0Vari : Integer; BeginIf (a.lenb.len) ThenBeginover := FALSE;Exit;End;If a.len b.len ThenBeginover := TRUE;Exit;End;For i := a.len DownTo 1 DoBeginIf a.num[i] b.num[i] ThenBeginover := FALSE;Exit;End;If a.num[i] b.num[i] ThenBeginover := TRUE;Exit;End;End;over := FALSE; End;

BeginReadln(s);FillChar(target.num, SizeOf(target.num), 0);target.len := Length(s);For i := 1 To target.len Dotarget.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;Repeatmiddle := average(left, right);If over(times(middle, middle), target)Then right := middleElse left := middle;Until over(plustwo(left), right);For i := left.len DownTo 1 DoWrite(left.num[i]);Writeln;End.

写一个java程序,用二分法把6插入到数组[1,2,5,7,8,9,13]

public static void insertSort(int[] data, int num) {

int left, right;

int middle, j;

// 准备

left = 0;

right = data.length - 2;

// 二分法查找插入位置

while (right = left) {

// 指向已排序好的中间位置

middle = (left + right) / 2;

if (num data[middle])

right = middle - 1;// 插入的元素在右区间

else

left = middle + 1; // 插入的元素在左区间

}

// 后移排序码大于R[i]的记录

for (j = data.length - 2; j = left; j--) {

data[j + 1] = data[j];

}

// 插入

data[left] = num;

}

public static void main(String[] args) {

int[] data1 = { 1, 2, 5, 7, 8, 9, 13, 0 };// 预留一位给需要排序插入的使用

//insertSort(data1, 0);

insertSort(data1, 6);

//insertSort(data1, 14);

for (int i = 0; i data1.length; i++) {

System.out.println(data1[i]);

}

}

用二分法查找（折半查找）java

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：查找序列是顺序结构，有序。

过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

利用循环的方式实现二分法查找

public class BinarySearch {

public static void main(String[] args) {

// 生成一个随机数组        int[] array = suiji();

// 对随机数组排序        Arrays.sort(array);

System.out.println("产生的随机数组为： " + Arrays.toString(array));

System.out.println("要进行查找的值： ");

Scanner input = new Scanner(System.in);

// 进行查找的目标值        int aim = input.nextInt();

// 使用二分法查找        int index = binarySearch(array, aim);

System.out.println("查找的值的索引位置： " + index);

}

/**     * 生成一个随机数组     *

* @return 返回值，返回一个随机数组     */

private static int[] suiji() {

// random.nextInt(n)+m  返回m到m+n-1之间的随机数        int n = new Random().nextInt(6) + 5;

int[] array = new int[n];

// 循环遍历为数组赋值        for (int i = 0; i array.length; i++) {

array[i] = new Random().nextInt(100);

}

return array;

}

/**     * 二分法查找  ---循环的方式实现     *

* @param array 要查找的数组     * @param aim 要查找的值     * @return 返回值，成功返回索引，失败返回-1     */

private static int binarySearch(int[] array, int aim) {

// 数组最小索引值        int left = 0;

// 数组最大索引值        int right = array.length - 1;

int mid;

while (left = right) {

mid = (left + right) / 2;

// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围            if (aim array[mid]) {

right = mid - 1;

// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围            } else if (aim array[mid]) {

left = mid + 1;

// 若查找数据与中间元素值正好相等，则放回中间元素值的索引   } else {

return mid;

}

}

return -1;

}}

运行结果演示：

由以上运行结果我们得知，如果要查找的数据在数组中存在，则输出该数据在数组中的索引；如果不存在则输出 -1 ，也就是打印 -1 则该数在数组中不存在，反之则存在。

四、利用递归的方式实现二分法查找

public class BinarySearch2 {

public static void main(String[] args) {

// 生成一个随机数组        int[] array = suiji();

// 对随机数组排序        Arrays.sort(array);

System.out.println("产生的随机数组为： " + Arrays.toString(array));

System.out.println("要进行查找的值： ");

Scanner input = new Scanner(System.in);

// 进行查找的目标值        int aim = input.nextInt();

// 使用二分法查找        int index = binarySearch(array, aim, 0, array.length - 1);

System.out.println("查找的值的索引位置： " + index);

}

/**     * 生成一个随机数组     *     * @return 返回值，返回一个随机数组     */

private static int[] suiji() {

// Random.nextInt(n)+m  返回m到m+n-1之间的随机数        int n = new Random().nextInt(6) + 5;

int[] array = new int[n];

// 循环遍历为数组赋值        for (int i = 0; i array.length; i++) {

array[i] = new Random().nextInt(100);

}

return array;

}

/**     * 二分法查找 ---递归的方式     *     * @param array 要查找的数组     * @param aim   要查找的值     * @param left  左边最小值     * @param right 右边最大值     * @return 返回值，成功返回索引，失败返回-1     */

private static int binarySearch(int[] array, int aim, int left, int right) {

if (aim array[left] || aim array[right]) {

return -1;

}

// 找中间值        int mid = (left + right) / 2;

if (array[mid] == aim) {

return mid;

} else if (array[mid] aim) {

//如果中间值大于要找的值则从左边一半继续递归            return binarySearch(array, aim, left, mid - 1);

} else {

//如果中间值小于要找的值则从右边一半继续递归            return binarySearch(array, aim, mid + 1, array.length-1);

}

}}

运行结果演示：

总结：

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~

Java二分法

首先得告诉你，二分法的前提是必须是顺序方式存储，而且必须是排好序了的。比如要从100个数中查找某一个数，前提是这一百个数是排好序（这里假如从小到大）的，然后找到最中间的数，若最中间的数（这里是第50个）比你要找的这个数大那你只需要在1到49个数里找，然后再取最中间的数，再判断，如此往复下去，最多次数，你算算看，

二分法逻辑及实现

二分法是通过递归的方法，不断地以二分的形式，缩小比较空间，以达到快速查找某个值是在列表中哪个位置的方法

二分法java递归的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于二分法 Java、二分法java递归的信息别忘了在本站进行查找喔。