算法-常见查找

1 顺序查找

挨个从下标0 - N挨个遍历，找出结果，没什么好说的.直接上代码.

/**
     * 顺序查找. 时间复杂度为 O(n)
     * @param values
     */
    public static final int findByOrder(int []arrays,int value) {
        
        for(int i = 0 ; i < arrays.length; i++) {
            if(arrays[i] == value) {
                return i;
            }
        }
        System.out.println("顺序查找结束，但并未找到相关数据");
          return -1;
    }

2 二分法查找

最终的目标是希望a[mid] = value,mid = (lowIndex + hightIndex) / 2, 如果value > a[mid] 显然 在中间下标的右侧，那么 lowIndex = mid + 1;在左侧那么hightIndex = mid - 1;+1，-1是因为没找到的情况下，mid并不是目标。

/**
     * 二分法查找.log2(n+1)
     * @param arrays
     * @param value
     */
    public static int findBySecondBinary(int arrays[],int value) {
        
        int lowIndex = 0;
        int highIndex = arrays.length - 1;
        int length = arrays.length; 
        while(lowIndex <= highIndex) {
                
            int mid = (lowIndex + highIndex) / 2;
            if(arrays[mid] == value) {
                return mid;
            }
            
            if(arrays[mid] > value) {
                highIndex = mid - 1;
            }else {
                lowIndex = mid + 1;
            }           
        }
        //System.out.println("二分法查找结束，但并未找到相关数据");
        
        return -1;
    }

3 插值查找

插值查找说白了，差值法查找，也是二分法的升级版. 适合分布比较较均匀的数组.

    public static int findByChaZhi(int a[],int value,int low ,int hight) {
        
        if(low > hight) {
            return -1;
        }
        
        int mid = low + (value - a[low]) / (a[hight] - a[low]) * (hight - low);
        if(a[mid] == value) {
            return mid;
        }
        
        if(value > a[mid]) {
            return findByChaZhi(a, value, mid + 1, hight);
        }
        if(value < a[mid]) {
            return findByChaZhi(a, value, low, mid - 1);
        }
        return -1;
    }

4 斐波拉契查找

斐波拉契，从第三个数开始每个数的值都等于前面两个数之和，数学公式f(k) = f(k - 1) + f(k-2) k >= 2, 其算法原理跟二分法都差不多，时间复杂度为logn, 最终都是要a[mid] = value,只是这次mid改为符合斐波拉契数列的方式计算 mid = low + f(k - 1) - 1; 斐波拉契将整个数组分成两段左边的长度用f(k - 1)表示，右边f(k - 2)，那么中间点应该是f(k - 1)位置，f(k - 1) - 1 是因为斐波拉契数列从1开始 而我们的数组下标从0开始.

//这个函数构建斐波拉契数列.
public static int[] getFeiboNaqiArrays(int nums) {
        int f[] = new int[nums];
        
        f[0] = 1;
        f[1] = 1;
        for(int i = 2; i < nums ;i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

      /**
     * 斐波那契查找，黄金查找法则.斐波那契数列 f(k) = f(k-1) + f(k-2) k >=2;0.618;
     * 时间复杂度Log2(n)
     * @param data
     * @param value.
     * @return
     */
    public static int findByFeiboNaqi(int data[],int value) {
        
        int low = 0;
        int hight = data.length - 1;
        int k = 0; //K表示斐波那契数组的索引.
        int f[] = getFeiboNaqiArrays(20);
        
        while(f[k] - 1 <= data.length) { 
            k++;
        }
        //请注意，这里很关键，得到一个斐波拉契长度大小的数组，超出data.length部分的元素，用data数组的最后一个补全.
        int temp[] = new int[f[k]];
        for(int i= 0 ; i < f[k] ; i++) {
            if(i < data.length) {
                temp[i] = data[i];
            }else {
                temp[i] = data[hight - 1];
            }
        }
        
        while(low <= hight) {
            int midIndex = low + f[k - 1] - 1;
            if(temp[midIndex] == value) {
                if(midIndex <= hight) {
                    return midIndex;
                }else {
                    return hight;
                }
            }
            
            if(temp[midIndex] > value) { //在左边
                //k--;
                hight = midIndex - 1;
                k-=1;
            }
            
            if(temp[midIndex] < value) {
                low = midIndex + 1;
                /*说明值在右边. 因为初始状态是f(k - 1)为左边，右边是f(k -2),
              那么右半段斐波拉契数组个数为 f(k - 3) + f(k - 4) ,分割点是          
              f(k - 3),下一次的mid = midIndex + 1 + f(k - 3) - 1;*/
                k-=2; 
            }   
        }
        return -1;
    }