Android中关于递归和二分法的算法实例代码
//1.实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回-1。
packagedemo;
publicclassMytest{
publicstaticvoidmain(String[]args){
int[]arr={1,2,5,9,11,45};
intindex=findIndext(arr,0,arr.length-1,12);
System.out.println("index="+index);
}
//1.实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回-1。
publicstaticintfindIndext(int[]arr,intleft,intright,intabc){
if(arr==null||arr.length==0){
return-1;
}
if(left==right){
if(arr[left]!=abc){
return-1;
}
}
intmid=left+(right-left)/2;//3//4
if(arr[mid]>abc){//
right=mid-1;
returnfindIndext(arr,left,right,abc);
}elseif(arr[mid]<abc){//5<45//9<45/11<45
left=mid+1;
returnfindIndext(arr,left,right,abc);//2,5//3,5//4.5
}else{
returnmid;
}
}
}
/1.实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回-1。
//array升虚数组
publicintfind(int[]array,intn){
if(array==null){
return-1;
}
intlen=array.length;
if(n<array[0]||n>array[len-1]){
return-1;
}
intleft=0;
intright=len-1;
while(left<right){
intmid=left+(right-left)/2;
if(array[mid]==n){
returnmid;
}elseif(array[mid]<n){
left=mid+1;
}else{
right=mid-1;
}
}
if(array[left]==n){
returnleft;
}else{
returnright;
}
}
//2.写一个函数将一个数组转化为一个链表。
//要求：不要使用库函数，(如List等)
publicstaticclassNode{
Nodenext;
intdata;
}
//返回链表头
publicNodeconvert(int[]array){
if(array==null||array.length==0){
returnnull;
}
Nodehead=newNode();
head.data=array[0];
intlen=array.length;
Nodeend=head;
for(inti=1;i<len;i++){
end=addNode(end,array[i]);
}
returnhead;
}
//给链表尾部添加一个节点
publicNodeaddNode(Nodeend,intdata){
Nodenode=newNode();
node.data=data;
end.next=node;
returnnode;
}
//3.有两个数组，[1,3,4,5,7,9]和[2,3,4,5,6,8],用上面的函数生成两个链表linkA和
//linkB，再将这两个链表合并成一个链表,结果为[1,2,3,4,5,6,7,8,9].
//要求：不要生成第三个链表，不要生成新的节点。
//3.1使用递归方式实现
//
publicNodecomb(int[]arrayA,int[]arrayB){
NodelinkA=convert(arrayA);
NodelinkB=convert(arrayB);
Nodehead;
if(linkA.data==linkB.data){
head=linkA;
linkA=linkA.next;
linkB=linkB.next;
head.next=null;
}elseif(linkA.data<linkB.data){
head=linkA;
linkA=linkA.next;
head.next=null;
}else{
head=linkB;
linkB=linkB.next;
head.next=null;
}
Nodeend=head;
comb(end,headA,headB);
returnhead;
}
//实现递归
publicvoidcomb(Nodeend,NodeheadA,NodeheadB){
if(headA==null&&headB==null){
return;
}elseif(headA==null){
end.next=headB;
return;
}elseif(headB==null){
end.next=headA;
return;
}
if(headA.data<headB.data){
end.next=headA;
headA=headA.next;
end=end.next;
end.next=null;
comb(end,headA,headB);
}elseif(headA.data==headB.data){
end.next=headA;
headA=headA.next;
headB=headB.next;
end=end.next;
end.next=null;
comb(end,headA,headB);
}else{
end.next=headB;
headB=headB.next;
end=end.next;
end.next=null;
comb(end,headA,headB);
}
}
//3.2使用循环方式实现
//循环实现
publicNodecomb(int[]arrayA,int[]arrayB){
//转换链表
NodelinkA=convert(arrayA);
NodelinkB=convert(arrayB);
//获取头节点
Nodehead;
if(linkA.data==linkB.data){
head=linkA;
linkA=linkA.next;
linkB=linkB.next;
head.next=null;
}elseif(linkA.data<linkB.data){
head=linkA;
linkA=linkA.next;
head.next=null;
}else{
head=linkB;
linkB=linkB.next;
head.next=null;
}
Nodeend=head;
//依次将较小的节点加到链表尾部
while(headA!=null&&headB!=null){
if(headA.data<headB.data){
end.next=headA;
headA=headA.next;
end=end.next;
end.next=null;
}elseif(headA.data==headB.data){
end.next=headA;
headA=headA.next;
headB=headB.next;
end=end.next;
end.next=null;
}else{
end.next=headB;
headB=headB.next;
end=end.next;
end.next=null;
}
}
//如果其中一个链表为空，将另外一个链表直接添加到合成链表尾部
if(headA==null){
end.next=headB;
}elseif(headB==null){
end.next=headA;
}
returnhead;
}
以上所述是小编给大家介绍的Android中关于递归和二分法的算法实例代码，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的，在此也非常感谢大家对毛票票网站的支持！