Android中关于递归和二分法的算法实例代码

概述//1.实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回-1。

// 1. 实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回 -1。

package demo;public class Mytest {public static voID main(String[] args) {int[] arr={1,2,5,9,11,45};int index=findindext(arr,arr.length-1,12);System.out.println("index="+index);}// 1. 实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回 -1。public static int findindext(int[] arr,int left,int right,int abc){if(arr==null||arr.length==0){return -1;}if(left==right){if(arr[left]!=abc){return -1;}}int mID=left+(right-left)/2;//3//4if(arr[mID]>abc){//right=mID-1;return findindext(arr,left,right,abc);}else if(arr[mID]<abc){//5<45//9<45/11<45left=mID+1;return findindext(arr,abc);//2,5//3,5//4.5}else{return mID;}}}/ 1. 实现一个函数，在一个有序整型数组中二分查找出指定的值，找到则返回该值的位置，找不到返回 -1。// array 升虚数组public int find(int[] array,int n){if(array == null){return -1;}int len = array.length;if(n < array[0] || n > array[len-1]){return -1;}int left = 0;int right = len -1;while(left < right){int mID = left + (right - left) / 2;if(array[mID] == n){return mID;}else if(array[mID] < n){left = mID + 1;}else{right = mID - 1;}}if (array[left] == n){return left;} else {return right;}}// 2. 写一个函数将一个数组转化为一个链表。// 要求：不要使用库函数，(如 List 等)public static class Node{Node next;int data;}// 返回链表头public Node convert(int[] array){if(array == null || array.length == 0){return null;}Node head = new Node();head.data = array[0];int len = array.length;Node end = head;for(int i=1; i< len ; i++){end = addNode(end,array[i]);}return head;}// 给链表尾部添加一个节点public Node addNode(Node end,int data){Node node = new Node();node.data = data;end.next = node;return node;}// 3. 有两个数组，[1,3,4,7,9] 和 [2,6,8],用上面的函数生成两个链表 linkA 和// linkB，再将这两个链表合并成一个链表,结果为[1,8,9].// 要求：不要生成第三个链表，不要生成新的节点。// 3.1 使用递归方式实现// public Node comb(int[] arrayA,int[] arrayB){Node linkA = convert(arrayA);Node linkB = convert(arrayB);Node head;if(linkA.data == linkB.data){head = linkA;linkA = linkA.next;linkB = linkB.next;head.next = null;}else if (linkA.data < linkB.data){head = linkA;linkA = linkA.next;head.next = null;}else {head = linkB;linkB = linkB.next;head.next = null;}Node end = head;comb(end,headA,headB);return head;}// 实现递归public voID comb(Node end,Node headA,Node headB){if(headA == null && headB == null){return;}else if(headA == null){end.next = headB;return;}else if(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,headB);}else if(headA.data == headB.data){end.next = headA;headA = headA.next;headB = headB.next;end = end.next;end.next = null;comb(end,headB);}else {end.next = headB;headB = headB.next;end = end.next;end.next = null;comb(end,headB);}}// 3.2 使用循环方式实现// 循环实现public Node comb(int[] arrayA,int[] arrayB){// 转换链表Node linkA = convert(arrayA);Node linkB = convert(arrayB);// 获取头节点Node head;if(linkA.data == linkB.data){head = linkA;linkA = linkA.next;linkB = linkB.next;head.next = null;}else if (linkA.data < linkB.data){head = linkA;linkA = linkA.next;head.next = null;}else {head = linkB;linkB = linkB.next;head.next = null;}Node end = head;// 依次将较小的节点加到链表尾部while(headA != null && headB != null){if(headA.data < headB.data){end.next = headA;headA = headA.next;end = end.next;end.next = null;}else if(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;}else if(headB == null){end.next = headA;}return head;}

以上所述是小编给大家介绍的AndroID中关于递归和二分法的算法实例代码，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的，在此也非常感谢大家对编程小技巧网站的支持！

总结

以上是内存溢出为你收集整理的Android中关于递归和二分法的算法实例代码全部内容，希望文章能够帮你解决Android中关于递归和二分法的算法实例代码所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。