关于java:Java实现查找算法线性折半插值斐波那契

20次阅读

共计 5358 个字符，预计需要花费 14 分钟才能阅读完成。

查找算法

线性查找

  • 基本思路：线性查找是最简略的查找办法，也很好了解，就是对一组有序 / 无序的序列进行遍历，一一比拟，直到找到对应的值
  • 代码如下：
public class LinearSearch {
    /**
 * * @param arr 要查找的数组
 * @param findVal 要查找的值
 * @return 返回对应值的下标，如果没有返回 -1
 */ public static int linearSearch(int[] arr, int findVal){if (arr == null || arr.length <= 0) return -1;
 for (int i = 0; i < arr.length; i ++){if (arr[i] == findVal)
                return i;
 }
        return -1;
 }
    public static void main(String[] args) {int[] arr = {128,321,23,4,19,23,10,98,100};
 int result = linearSearch(arr, 10);
 System.out.println(result);
 }
}

折半查找

  • 介绍：折半查找也叫二分查找，要实现折半查找必须满足两个要求，第一是数列要有序的，第二是寄存数列的容器是按序寄存的

  • 基本思路：

    • 1）确定数组的两头下标 mid，等于右边下标 left+ 左边下标 right 的一半，mid = (left + right) / 2

    • 2）把要找的值 findVal 和下标 mid 对应的值 midVal 进行比拟

      • 如果 findVal 大于 midVal，则表明要找的数在左边，向右查找，此时的 left 为 mid + 1，right 不变，从新计算 mid
      • 如果 findVal 小于 midVal，则表明要找的数在右边，向左查找，此时的 right 为 mid – 1，left 不变，从新计算 mid
      • 如果下面两个条件都不满足，证实 findVal 等于 midVal，则间接返回 mid 下标
    • 3）如果说 left > right，证实咱们要找的数不存在，间接返回 -1

  • 举例说明：比方有序数组{1,8,9,10,29,39,49,69}，查找 39

    • 如上图所示，第一次并没有找到 findVall，第二次 left,mid 从新调整过后, 找到了 findVal

  • 代码如下：

    • 这里应用的是递归的形式实现折半查找
/**
 * 应用折半查找的前提是该数组是有序的
 */
public class BinarySearch {public static int binarySearch(int[] arr, int findVal){if (arr == null || arr.length <= 0) return -1;
 return binarySearch(arr, 0, arr.length - 1, findVal);
 }
    public static int binarySearch(int[] arr, int left, int right, int findVal){if (left > right) return -1;
 int mid = (left + right) / 2;
 int midVal = arr[mid];
 if (findVal < midVal){return binarySearch(arr, left, mid - 1, findVal);
 }else if (findVal > midVal){return binarySearch(arr, mid + 1, right, findVal);
 }else {return mid;}
    }
    public static void main(String[] args) {int[] arr = {1,4,9,29,98,100,989};
 int result = binarySearch(arr, 10);
 System.out.println(result);
 }
}

插值查找

  • 介绍 ：插值查找是相似于折半查找，不同的中央在于 mid 的计算不同，折半查找是每次从取两头值，而插值查找每次从 自适应 mid处开始查找

  • 基本思路：

    • 与折半查找雷同，mid 的计算形式不同
    • mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

  • 举个例子：比方有序数组{1,8,9,10,29,39,49,69}，查找 39

    • 如上图所示，经验了三次查找才找到了 findVal
    • 这里用的例子因为数组外面的整数比拟没有法则，所以通过了三次查找才找到，而折半查找只用了两次就找到了。然而如果是对于一组有法则的有序序列来说，查找的次数往往只须要一次（大家能够试一下从 1 -100 外面去查找一个数）

  • 代码如下：

    • 这里也是采纳递归的形式实现，留神看一下上面的正文
public class InsertSearch {public static int insertSearch(int[] arr, int findVal){if (arr == null || arr.length <= 0) return -1;
 return insertSearch(arr, 0, arr.length - 1, findVal);
 }
    /**
 ** @param arr 有序数组
 * @param left 右边的下标
 * @param right 左边的下标
 * @param findVal 要找的值
 * @return findVal 对应的下标，如果找不到则返回 -1
 */ public static int insertSearch(int[] arr, int left, int right, int findVal){
        // 以下三个判断条件必须写
 // 第一个：当找不到的时候 left 会大于 right
 // 第二个和第三个：如果说要找的值不在该数组的最大值和最小值的范畴里（对于升序的数组来说）// 那么如果不加这两个条件，可能会导致最初算进去的 mid 不在 left 和 right 之间
 if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) return -1;
 int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
 int midVal = arr[mid];
 if (findVal > midVal){return insertSearch(arr, mid + 1, right, findVal);
 }else if (findVal < midVal){return insertSearch(arr, left, mid - 1, findVal);
 }else {return mid;}
    }
    public static void main(String[] args) {int[] arr = {1,8,9,10,29,39,49,69};
 System.out.println(Arrays.toString(arr));
 int result = insertSearch(arr, 39);
 System.out.println(result);
 }
}

斐波那契查找

  • 介绍：利用斐波那契数列找到数组中的黄金分割点

    • 黄金分割点：是指把一条线段宰割为两局部，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是 0.618。
    • 斐波那契数列中，两个相邻数的比例是有限靠近与黄金分割值 0.618
    • 斐波那契数列计算公式：F(k) = F(k-1) + F(k-2),F(1)=1,F(2)=2

  • 基本思路：

    • 该查找算法与折半查找相似，区别也是在于 mid 的计算，mid 是取位于黄金分割点左近，即 mid=low+F(k-1)-1

  • F(k-1)是什么？

    • 由 F(k)计算公式的性质, 能够失去 F(k)-1 = (F(k-1) – 1) + (F(k-2) – 1) + 1
    • 也就是说，只有数组的长度为 F(k)-1，就能够将该表分成长度为 F(k-1) – 1 和 F(k-2) – 1 两段
    • 而两头地位 mid = low + F(k – 1) – 1
  • 是否须要扩容数组：数组的长度 n 不肯定等于 F(k)，所以须要将原来的数组长度 n 减少至 F(k)，不肯定要齐全相等，只有比 F(k)大就行，所以当 n 增大后就须要进行扩容
  • K 如何确定？ 代码如下：
while(n > F(k))
    k++

  • 举个例子：比方有序数组{1,8,9,10,29,39,49,69}，查找 39

    • 1）首先判断是否须要扩容，n 为 8，k 为 5，F(5)=8，n 刚好等于 5，不须要扩容

    • 2）第一轮，依据公式计算出 mid=4，arr[mid]=29，小于 39, 向右查找

      • left = mid + 1 = 5
      • right = 7
      • k = k – 2 = 3（为什么须要 k -2，看上面的解释）
      • mid = 6

    • 3）第二轮，arr[mid] = arr[6] = 49，大于 39，向左查找

      • left = 5
      • right = mid – 1 =6
      • k = k – 1 =2（为什么须要 k -1，看上面的解释）
      • mid = 5
    • 4）第三轮，arr[mid] = arr[5] = 39，等于 39，找到了

  • k -= 2 和 k – 的含意：

    • 如上图所示，f(k)- 1 能够分成两段，别离是 f(k-1)- 1 和 f(k-2)-1
    • 当要找的数比 arr[mid]小，咱们就把 f(k)- 1 的长度缩减成 f(k-1)-1，所以此时 k –
    • 当要找的数比 arr[mid]大，咱们就把 f(k)- 1 的长度缩减成 f(k-2)-1，所以此时 k -= 2
  • 代码如下：
public class FibonacciSearch {
    private static int maxSize = 100;
 private static int count = 0;
 private static int[] fib(){int[] f = new int[maxSize];
 f[0] = 1;
 f[1] = 1;
 for (int i = 2; i <= maxSize - 1; i ++){f[i] = f[i - 1] + f[i - 2];
 }
        return f;
 }
    // 斐波那契查找算法
 public static int fibSearch(int[] arr, int findVal){return fibSearch(arr, 0, arr.length - 1, findVal);
 }
    /**
 * * @param arr 有序数组
 * @param low 数组右边的下标
 * @param high 数组左边的下标
 * @param findVal 要查找的值
 * @return 找到的值对应的下标，如果没有返回 -1
 */ public static int fibSearch(int[] arr, int low, int high, int findVal){if (arr == null || arr.length <= 0) return - 1;
 int k = 0; // 示意斐波那契数列的下标
 int[] f = fib(); // 获取斐波那契数列
 int mid = 0; //mid 值
 // 获取斐波那契宰割数值
 while (high > f[k] - 1){k ++;}
        // 把 k 与 n 进行比拟，如果 n 小就须要进行扩容
 int[] temp = Arrays.copyOf(arr, f[k]);
 // 把扩容多进去的数赋予原来 arr 的最初一个数据
 for (int i = high + 1; i < temp.length; i ++){temp[i] = arr[high];
 }
        System.out.println("查找之前的工作：");
 System.out.println("t 扩容后的数组 arr：" + Arrays.toString(temp));
 System.out.println("tleft：" + low);
 System.out.println("tright：" + high);
 System.out.println("tk：" + k);
 // 应用 while 循环，找到咱们的数 Key
 while (low <= high){
            // 设置两头点
 mid = low + f[k-1] - 1;
 System.out.println("这是第" + ++count +"轮：");
 System.out.println("tleft：" + low);
 System.out.println("tright：" + high);
 System.out.println("tk：" + k);
 System.out.println("tf[k-1]-1：" + (f[k-1] -1));
 System.out.println("tmid：" + mid);
 if (findVal < temp[mid]){
                high = mid - 1;
 // 这里为什么是 k --
 //1、全副元素 = 后面的元素 + 后边的元素
 //2、f(k) = f(k-1) + f(k-2)
 //3、后面有 f(k-1)个元素，所以能够持续拆分，f(k-1) = f(k-2)+f(k-3)
 k --;
 }else if (findVal > temp[mid]){
                low = mid + 1;
 // 为什么是 k -= 2
 //1、全副元素 = 后面的元素 + 前面的元素
 //2、f(k) = f(k-1) + f(k-2)
 //3、因为咱们有 f[k-2]，所以能够持续拆分 f[k-2]=f[k-3]+f[k-4]
 //4、即在 f[k-2]的后面进行查找
 //5、下次循环 mid = f[k - 1 - 2] - 1
 k -= 2;
 }else {if (mid <= high){return mid;}else {return high;}
            }
        }
        return -1;
 }
    public static void main(String[] args) {int[] arr = {1,8,9,10,29,39,49,69};
 int resultIndex = fibSearch(arr, 39);
 System.out.println(resultIndex);
 }
}

正文完
java
发表至： java
2020-09-18
 0
关于java:List-去重的-6-种方法这个方法最完美
关于java:Java-亿级项目架构设计与落地应用完结渚清沙白鸟飞回
关于java:netty系列之HashedWheelTimer一种定时器的高效实现
关于java:Spring-Boot-综合应用