// 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,0,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//4 if(arr[mid]>abc){// right=mid-1; return findIndext(arr,left,right,abc); }else if(arr[mid]<abc){//5<45//9<45/11<45 left=mid+1; return findIndext(arr,left,right,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,5,7,9] 和 [2,3,4,5,6,8],用上面的函数生成两个链表 linkA 和 // linkB，再将这两个链表合并成一个链表,结果为[1,2,3,4,5,6,7,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, headA, headB); }else if(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 使用循环方式实现 // 循环实现 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中关于递归和二分法的算法实例代码，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的，在此也非常感谢大家对脚本之家网站的支持！