二分查找的非遞歸、遞歸實作及其優化

/**
 * 二分查找的非遞歸、遞歸實作及其優化
 * 算法要求序列有序
 * 1、折半查找是進行加法與除法運算的（mid=(low+high)/2）
 * 2、插值查找則進行更複雜的四則運算（mid = low + (high - low) * ((key - a[low]) / (a[high] - a[low]))）
 * 3、而斐波那契查找隻進行最簡單的加減法運算（mid = low + F[k-1] - 1）,在海量資料的查找過程中，這種細微的差别可能會影響最終的效率。
 * 是以就執行效率來說3>1>2
 * @author fwk
 */
public class BinaryChop {
    public static void main(String[] args) {
        int [] n = {,,,,,};
        System.out.println(chop(n, ));
        System.out.println(chop2(n, ,,n.length-));
        System.out.println(chop3(n, ));
        System.out.println(chop4(n, ));
    }

    /**
     * 非遞歸實作
     * 找到時傳回下标，找不到時傳回-1
     * @param array 目标數組（遞增數組）
     * @param point 需要查找的數字
     * @return
     */
    public static int chop(int[] array,int point){
        if(array.length==||array==null) return -;  //處理空數組和空指針
        else{
            int low = ,high = array.length-,num = -;
            while(low<=high){
                int mid = (low+high)/;              //取中點
                if(array[mid]==point){
                    num = mid;
                    break;
                }else if(array[mid]<point) low=mid+;   //中點右移
                else high=mid-;                        //中點左移
            }
            return num;
        }
    }

    /**
     * 遞歸實作二分查找
     * @param array
     * @param point
     * @param low
     * @param high
     * @return
     */
    public static int chop2(int[] array,int point,int low,int high){
        //注:此處也應做數組非空檢查 
        int mid = (low+high)/;
        if(low>high||point<array[low]||point>array[high]) return -;
        if(array[mid]==point) return mid;
        else if(array[mid]>point) return chop2(array, point, low, high-);
        else return chop2(array, point, low+, high);
    }

    /**
     * 優化1:插值查找
     * 插值查找算法對二分查找算法的改進主要展現在mid的計算上
     * 計算公式為:mid = ((point-array[low])/(array[high]-array[low]))*(high-low)+low
     * @param array
     * @param point
     * @return
     */
    public static int chop3(int[] array,int point){
        if(array.length==||array==null) return -;  //處理空數組和空指針
        else{
            int low = ,high = array.length-,num = -;
            while(low<high){
                int mid = ((point-array[low])/(array[high]-array[low]))*(high-low)+low;
                if(array[mid]==point){
                    num = mid;
                    break;
                }else if(array[mid]<point) low=mid+;   //中點右移
                else high=mid-;                        //中點左移
            }
            return num;
        }
    }

    /**
     * 優化2:斐波那契查找
     * @param array
     * @param point
     * @return
     */
    public static int chop4(int[] array,int point){
        int [] F = {,,,,,,,,,};     //構造斐波那契數列
        int low, high, mid, k,n=array.length-;  //n為待查找數組的長度
        low = ;
        high = n;
        k = ;
        while (n > F[k]-) /* 計算n位于斐波那契數列的位置 */
            k++;
        while (low <= high) {
            mid = low + F[k-] -;
            if (point < array[mid]){
                high = mid - ;
                k = k - ;
            }
            else if (point > array[mid]){
                low = mid + ;
                k = k - ;
            }
            else {
                if (mid <= n)
                    return mid;
                else
                    return n;
            }
        }
        return ;
    }
}