查找算法总结

简单查找

java简单实现

package 经典;

public class SimpleSearch {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr={0,70,80,31,37,10,1,48,60,33,80};
        
        System.out.print(guardSearch(arr, 31));
    }
    
    public static int guardSearch(int arr[],int element){
        
        int i=arr.length-1;
        arr[0]=element;
        
        while(arr[0]!=arr[i--]) ;
        
        if(i!=0)
            return i+1;
        
        return -1;
    }
    
}

二分查找

java实现

package 经典;

public class BinarySearch {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int[] a={70,80,31,37,10,1,48,60,33,80};
            
        QuickSort.quickSort(a);
        
        System.out.println(binarySearch(a,31));
    }
    
    private static int binarySearch(int[] a, int element) {
        // TODO Auto-generated method stub
        
        int low,mid,upper;
        
        low=0;
        upper=a.length-1;
        
        while(low<=upper){
            mid=(low+upper)/2;
            
            if(a[mid]>element)
                upper=mid-1;
            else if(a[mid]<element)
                low=mid+1;
            else
                return mid;
        }
        
        return -1;
    }
}

费氏查找

java实现

package sort;

public class FibonacciSearch {
    public static int search(int[] number, int des) { 
        int[] fib = createFibonacci(number.length); 

        int x  = findX(fib, number.length+1, des);
        
        int m = number.length - fib[x]; 
        
        x--; 
        int i = x; 

        if(number[i] < des) 
            i += m; 

        while(fib[x] > 0) { 
            if(number[i] < des) 
                i += fib[--x]; 
            else if(number[i] > des) 
                i -= fib[--x]; 
            else 
                return i; 
        } 
        
        return -1; 

    }
    
    private static int[] createFibonacci(int max) {
        int[] fib = new int[max];
        for(int i = 0; i < fib.length; i++) {
            fib[i] = Integer.MIN_VALUE;   
        }

        fib[0] = 0; 
        fib[1] = 1; 

        for(int i = 2; i < max; i++) 
            fib[i] = fib[i-1] + fib[i-2];
        
        return fib;
    }
    
    private static int findX(int[] fib, int n, int des) {
        int i = 0; 

        while(fib[i] <= n) 
            i++; 

        i--; 
        
        return i;     
    }
    
    public static void main(String[] args) {
        int[] number = {1, 4, 2, 6, 7, 3, 9, 8};
        
        QuickSort.quickSort(number);
        
        int find = FibonacciSearch.search(number, 3);
        
        if(find != -1) 
            System.out.println("找到數值於索引 " + find); 
        else 
            System.out.println("找不到數值"); 
    }
    
}