正文
JAVA二分法查找伪代码 java实现二分查找
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
java 二分法 排序
二分排序就是用先用二分查找法来查某一个元素JAVA二分法查找伪代码，然后再用别JAVA二分法查找伪代码的排序算法来进行排序。
package insert;
public class InsArrayApp {
public static void main(String[] args) {
int size = 100;
InsArray arr = new InsArray(size);
arr.insert(10);
arr.insert(9);
arr.insert(8);
arr.insert(7);
arr.insert(6);
arr.insert(10);
arr.insert(9);
arr.insert(8);
arr.insert(5);
arr.insert(4);
arr.insert(3);
arr.insert(2);
arr.insert(1);
arr.display();
// arr.insertSort();
// arr.display();
// System.out.println(arr.median());
// arr.noDups();
arr.noDups2();
arr.display();
}
}
class InsArray {
private int[] a;
private int nElems;
public InsArray(int size) {
a = new int[size];
nElems = 0;
}
public void insert(int value) {
a[nElems] = value;
nElems++;
}
public void display() {
for (int i = 0; i nElems; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public void insertSort() {
int out, in;
int copy = 0;
int compare = 0;
/* for(out = 1;outnElems;out++){
int tmp = a[out];
in = out;
while(in0a[in-1]=tmp){
a[in] = a[in-1];
--in;
}
a[in] = tmp;
}*/
for(out = 1;outnElems;out++){
int tmp = a[out];
in = out;
while(in0){
if(a[in-1]=tmp){
a[in] = a[in-1];
--in;
++copy;
++compare;}
else{
break;
}
}
++compare;
a[in] = tmp;
}
System.out.println("copy:" + copy + "compare:" + compare);
}
public int median(){
insertSort();
int m = nElems/2;
return a[m];
}
public void noDups(){
insertSort();
/*
InsArray tmp = new InsArray(nElems);
for(int i = 0;inElems;i++){
for(int j = i+1;jnElems;j++)
if(a[i] == a[j]){
a[j] = -1;
}
if(a[i]!=-1)
tmp.insert(a[i]);
}
*/
InsArray tmp = new InsArray(nElems);
int i;
for(int j = 0;jthis.nElems;j++){
/*if(tmp.nElems==tmp.find(this.a[j])) //binary find
tmp.insert(this.a[j]);
else
continue;*/
for( i = 0; i tmp.nElems; i++) { // for each element
if(tmp.a[i]==this.a[j]) // found searchKey?
break;
}
if(i==tmp.nElems) // no
tmp.insert(this.a[j]);
}
this.a = tmp.a;
this.nElems = tmp.nElems;
}
public int find(long searchKey) {
int lowerBound = 0;
int upperBound = nElems-1;
int curIn;
while(true) {
curIn = (lowerBound + upperBound)/2;
if(a[curIn]==searchKey)
return curIn;
else if(lowerBoundupperBound)
return nElems;
else {
if(a[curIn]searchKey)
upperBound = curIn-1;
else
lowerBound = curIn+1;
}
}
}
public void noDups2(){
insertSort();
for(int i = 0;inElems;i++){
for(int j = i+1;jnElems;j++)
if(a[i] == a[j]){
a[j] = -1;
}
}
display();
int index = 0;
for(int i=0;inElems;i++){
if(a[i]!=-1){
index++;
}else{
for(int j=index+1;jnElems;j++){
if(a[j]!=-1){
a[index] = a[j];
a[j]=-1;
index++;
break;
}
}
}
}
nElems = index;
}
}
上面的代码，是我以前敲的，有个find()方法是二分查找，然后再用插入排序去进行排序。
相关问答
Q1: 关于java的binarySearch（）方法
结果是-6JAVA二分法查找伪代码的原因是在子串[2,3,4,5,6]中并未找到8这个数字。然后我们来看一下binrySearchJAVA二分法查找伪代码的源码
public static int binarySearch(int[] a, int fromIndex, int toIndex,
int key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low = high) {
int mid = (low + high) 1;
int midVal = a[mid];
if (midVal key)
low = mid + 1;
else if (midVal key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
可以从源码中看到JAVA二分法查找伪代码，真正的二分查找是在binarySearch0方法中进行的。每次循环都会计算出本轮的中间位置midJAVA二分法查找伪代码，以及获取中间值midVal。当中间值小于key时，说明要找的值在右半边，low等于mid+1，当中间值大于key说明在左半边，high=mid-1,找到了然后开始下一轮。当等于时也就是找到了目标值，直接返回位置mid。如果最后找不到目标值，则返回-(low+1)。
再来看看具体问题的执行：
第一轮算出的mid是(1+5) 1 =2，midValue=3 8 ,low=3；
进入第二轮mid为（3+5）1 =3,midValue=4 8 ,low=4；
进入第三轮mid为（4+5）1 = 4，midValue=5 8,low=5; 此时low==high跳出while循环 返回-（5+1）即-6.
拓展知识
二分查找的流程如下图：
Q2: 用二分法查找（折半查找）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);
}
}}
运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
Q3: 二分法的计算机应用
由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。
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.
Q4: java泛型 二分查找
以下代码是关于对象的 二分查找 的例子，已经测试通过，执行即可。
Student 是基本比较对象类
Dichotomy 是二分法执行类
Test 是测试类
package com.dichotomy;
public class Student implements ComparableStudent {
private int id;
private String name;
private String idCard;
private String sex;
private String mobile;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getIdCard() {
return idCard;
}
public void setIdCard(String idCard) {
this.idCard = idCard;
}
public String getSex() {
return sex;
}
public void setSex(String sex) {
this.sex = sex;
}
public String getMobile() {
return mobile;
}
public void setMobile(String mobile) {
this.mobile = mobile;
}
/**
* 排序控制
* @param o1 Student
* @param o2 Student
* @return int 返回 -1 向前移动, 1 向后移动, 0 不移动
* 这个方法需要自己进行调整，排序比较和二分查找时均使用此方法进行位置调整
* 比较时使用的key自己可以进行修改，不过要保证唯一性，否则查询出来的值会不准确
*/
public int compareTo(Student o) {
//不同的执行次序决定排序和查找次序不同,可以同下面的调换一下
if(this.getId() o.getId()){
return -1;
} else if(this.getId() == o.getId()){
;
} else {
return 1;
}
//不同的执行次序决定排序和查找次序不同
int c = this.getIdCard().compareTo(o.getIdCard());
if(c != 0){
return c;
}
//不同的执行次序决定排序和查找次序不同
int n = this.getName().compareTo(o.getName());
if(n != 0){
return n;
}
return 0;
}
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append(this.getId()).append("\t");
sb.append(this.getName()).append("\t");
sb.append(this.getIdCard()).append("\t");
sb.append(this.getMobile()).append("\t");
sb.append(this.getSex());
return sb.toString();
}
}
JAVA二分法查找伪代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java实现二分查找、JAVA二分法查找伪代码的信息别忘了在本站进行查找喔。
