数据结构之查找

Java中常用的查找有

• 线性查找
• 二分查找/折半查找
• 插值查找
• 斐波那契查找/黄金分割点查找

都是比较简单的，除了斐波那契查找

以下只给出思路与关键方法，算法的源代码放在了git中，需要的自取

leidl97/algorithm-src

二分查找

思想

必须为有序的，可以正序，也可以倒序

每次切一半，找到返回找不到向左右继续查

先按照给定数据的一半找起，如果目标值比mid大，则向右递归，反之，向左递归。

优化：可以查找重复数据，在找到元素之后，向左右依次进行比较，查找所有相同的元素

需要注意的是边界值问题 left必须为<=而不是<

代码实现

 private static void search(int[] arr,int left, int right, int act) {
     if (left <= right) {
         int mid = (left + right) / 2;
         if (arr[mid] > act) {
             search(arr, left, mid, act);
         } else if (arr[mid] < act) {
             search(arr,mid+1, right, act);
         } else {
             System.out.println("找到数据");
             list.add(arr[mid]);
             int i = mid+1;
             if (i < arr.length) {
                 while (arr[i++] == arr[mid]) {
                     System.out.println("找到数据");
                     list.add(arr[mid]);
                 }
             }
             int j = mid-1;
             if (j > 0) {
                 while (arr[j--] == arr[mid]) {
                     System.out.println("找到数据");
                     list.add(arr[mid]);
                 }
             }
             System.out.println("找到的数据有"+list.size()+"个");
         }
     } else {
         System.out.println("没有该数据");
     }
 }
复制代码

插值查找

与二分查找类似，主要解决二分查找的部分情况下效率不高的问题，比如一个1到10的数组，找最边上的1或者10那么就需要查找很多次

换言之就是找mid的方式改变，因数由1/2变为下面的，我也不知道怎么算出来的

那么，key就是你查找的目标值

将二分查找代码的这处替换即可

int mid = left + (right – left) * (act – arr[left]) / (arr[right] – arr[left])

所以说对于比较均匀的查找表来说，采用插值查找速度较快

不均匀的情况下，速度不一定比二分快

斐波那契查找

我愿称之为玄学查找，只是换了一个mid点，还贼难懂，快的话也没有哪一个能确切的说明，有的是说加减比乘除快，我没实际测试过，其实也就是换了个mid查找位置。

这个查找需要花费点时间，其实也就是改变了中间节点mid的位置

斐波那契查找也称为黄金分割法查找，将一条线段分割为两个部分，其中一部分比上全长之比等于另一部分与这部分之比，取其前三数字的近似值为0.618。

中间值不在由中间值或者插值得到，而是处于黄金分割点附近

F = { 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , . . . }

难点

1、为什么需要拆分为f(k-1) -1 而不是 f(k-1)？

需要找到黄金分割点，也就是mid点，可以按照此点作为判断的标志，方便进行向前向后进行查找，当然也可以另作定义，不过写起来会比较麻烦

花时间的点

2、为什么向前查找是k-1，向后查找是k-2

花时间的点

为什么斐波那契查找更有效率？

二分法采用的是除法，而这是加减法

代码实现

 public class FibonacciSearch {
     public static void main(String[] args) {
         int[] a = {1,8,10,89,1000,1234};
         sort(a,1234);
     }
     //{1,1,2,3,5,8,13,21}
     private static int[] fib() {
         int[] fib = new int[20];
         fib[0] = 1;
         fib[1] = 1;
         for (int i = 2; i < fib.length; i++) {
             fib[i] = fib[i-1] + fib[i-2];
         }
         return fib;
     }
 
     private static int sort(int[] arr, int act) {
         int low = 0;
         int high = arr.length - 1;
         int k = 0;//fib下标k
         int mid = 0;//黄金分割点
         int[] f = fib();//拿到斐波那契数列
         //获取到黄金分割点，数列长度大于数组长度且最接近的数组值
         while (high > f[k] - 1) {
             k++;
         }
         //f[k]的值可能大于数组长度，所以需要扩容。原数组的长度要接近斐波那契的值
         int[] temp = Arrays.copyOf(arr,f[k]-1);
         //将temp为0的位置填充
         for (int i = arr.length; i < temp.length; i++) {
             temp[i] = arr[high];
         }
         //循环查找
         while (low <= high) {
             mid = low + f[k-1] - 1; 
             if (act < temp[mid]) {
                 //向左查找
                 high = mid - 1;
                 //为什么是k--，全部 = 前面 + 后面，前面有F[K-1]个元素，可以继续拆分为f[k-2] + f[k-3]，在f[k-1]的前面继续查找
                 k--;
             } else if(act > temp[mid]){
                 //向右查找
                 low = mid + 1;
                 //为什么是k-2，全部 = 前面 + 后面，后面有f[k-2]个元素，将其拆分，需要在f[k-3]的位置进行查找，原来是k-1,现在是k-3所以要-2
                 k -= 2;
             } else {
                 //找到,需要进一步判断下标，防止越界
                 if (mid < high) {
                     System.out.println("找到元素,下标为："+mid);
                     return 0;
                 } else {
                     System.out.println("找到元素,下标为："+high);
                     return 0;
                 }
             }
         }
         System.out.println("未找到元素");
         return -1;
     }
 }
复制代码