Android 算法 關於遞歸和二分法的小算法，android二分法

Android 算法 關於遞歸和二分法的小算法，android二分法

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;
}