Java数据结构之二分查找/插值查找/斐波那契查找

偏执的太偏执、 2024-04-01 12:57 66阅读 0赞

**目录**

一.简单的线性查找

1.问题引出

2.代码实现

二.二分查找算法

1.基本介绍

2.代码实现(递归)

3.代码实现(非递归)

4.二分查找的功能完善

三.插值查找

1.简单介绍

2.代码实现(递归)

4.注意事项

四.斐波那契查找

1.基本介绍

2.代码实现(非递归)

--------------------

## 一.简单的线性查找 ##

### 1.问题引出 ###

有一个数列:\{1, 9, 45, 5, 69, 13, 58\}，判断数列中是否包含此数

【顺序查找】要求:如果找到了，就提示找到，并给出下标值

### 2.代码实现 ###

public class SeqSearch {
        public static void main(String[] args) {
            int[] arr = {1, 9, 45, 5, 69, 13, 58};
            int i = seqSearch(arr, 5);
            if (i == -1)
                System.out.println("未查找到");
            else
                System.out.println("下标为:" + i);
    
    
        }
    
        //线性查找
        public static int seqSearch(int[] arr, int value) {
            //线性查找是逐一比对,发现有相同值,就返回下标
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == value)
                    return i;
    
    
            }
            return -1;
    
        }
    }

**几种结果**

>     System.out.println(seqSearch(arr, 5));        ---------3
>     System.out.println(seqSearch(arr, 1));        ---------0         System.out.println(seqSearch(arr, 0));        ---------1

## 二.二分查找算法 ##

### 1.基本介绍 ###

**二分查找:**  
请对一个**有序数组**进行二分查找\{1,8，10，89，1000，1234\}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数”。

**二分查找的思路分析**  
1.首先确定该数组的中间的下标mid= (left +right) / 2  
2.然后让需要查找的数findval和arr\[mid\]比较  
2.1 findval>arr\[mid\]，说明你要查找的数在mid的右边,因此需要递归的向右查找

2.2 findval<arr\[mid\],说明你要查找的数在mid的左边,因此需要递归的向左查找

2.3 findval ==arr\[mid\]说明找到，就返回  
什么时候我们需要结束递归.  
1)找到就结束递归  
2)递归完整个数组，仍然没有找到findval,也需要结束递归当left>right就需要退出

### **2.代码实现(递归)** ###

//二分查找的数组必须是有序的
    public class BinarySearch {
        public static void main(String[] args) {
            int[] arr = {1, 8, 10, 89, 1000, 1000,1234};
            System.out.println(binarySearch(arr, 0, arr.length - 1, 1000));
    
        }
    
        public static int binarySearch(int[] arr, int left, int right, int value) {
            if (left > right)
                return -1;
            int mid = (left + right) / 2;
            if (arr[mid] == value)
                return mid;
            else if (arr[mid] > value) {
                //向左递归
                return binarySearch(arr, left, mid - 1, value);
            } else {
                //向右递归
                return binarySearch(arr, mid + 1, right, value);
            }
    
    
        }
    }

**几种结果**

>     System.out.println(binarySearch3(arr,0,arr.length-1,1234));  ------6
> 
>     System.out.println(binarySearch3(arr,0,arr.length-1,1));     ------1
> 
>     System.out.println(binarySearch3(arr,0,arr.length-1,567));  ------(-1)

### **3.代码实现(非递归)** ###

public static int binarySearch3(int[] arr, int value) {
            int left = 0;
            int right = arr.length - 1;
            int mid;
            while (left <= right) {
                mid = (left + right) / 2;
                if (arr[mid] > value) {//向左找
                    right = mid - 1;
                } else if (arr[mid] < value) {//向右找
                    left = mid + 1;
                } else {
                    return mid;
                }
    
            }
            return -1;
    
    
        }

**几种结果**

>     System.out.println(binarySearch3(arr,1234));  ------6
> 
>     System.out.println(binarySearch3(arr,1));     ------1
> 
>     System.out.println(binarySearch3(arr,567));  ------(-1)

### 4.二分查找的功能完善 ###

问题引出:\{1,8，10，89，1000，1000，1234\}当一个有序数组中，有多个相同的数值时,如何将所有的数值都查找到，比如这里的1000,应该返回4,5

**代码实现(递归)**

//二分查找的数组必须是有序的
    public class BinarySearch {
        public static void main(String[] args) {
            int[] arr = {1, 8, 10, 89, 1000, 1000,1234};
            System.out.println(binarySearch2(arr, 0, arr.length - 1, 100));
    
        }
    
       
        public static List<Integer> binarySearch2(int[] arr, int left, int right, int value) {
            List<Integer> list = new ArrayList<>();
            if (left > right){
                list.add(-1);
                return list;
            }
    
            int mid = (left + right) / 2;
            if (arr[mid] == value){
                list = new ArrayList<>();
                list.add(mid);
                int temp=mid-1;
                while(temp>=0&&value==arr[temp]){
                    list.add(temp);
                    temp--;
                }
                temp=mid+1;
                while(temp<arr.length&&value==arr[temp]){
                    list.add(temp);
                    temp++;
                }
                return list;
            }
    
            else if (arr[mid] > value) {
                //向左递归
                return binarySearch2(arr, left, mid - 1, value);
            } else {
                //向右递归
                return binarySearch2(arr, mid + 1, right, value);
            }
    
    
        }
    }

**几种结果**

>     System.out.println(binarySearch2(arr, 0, arr.length - 1, 100));  ----(-1)
> 
>     System.out.println(binarySearch2(arr, 0, arr.length - 1, 1000));   ----[5, 4]

## 三.插值查找 ##

### 1.简单介绍 ###

**折半查找的缺点:**

当我们查找1--100的数中的1的时候,显然mid=50,一直折半查找步骤很多,我们是否可以找到一个合适的值来作为mid减少折半的次数呢?

1)插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。  
2）将折半查找中的求mid索引的公式, low表示左边索引, high表示右边索引.

![e7d2709f9b1e41d6a6af4b368fcaa7b1.png][]

3) int midlIndex = low +(high - low)\* (key - arr\[low\])/ (arr\[high\] - arr\[low\])

### 2.代码实现(递归) ###

public class InsertSort {
        public static void main(String[] args) {
            int[] arr=new int[100];
            for(int i=0;i<100;i++){
                arr[i]=i+1;
            }
            System.out.println(insertValueSearch(arr, 0, arr.length - 1, 1));
    
        }
        //编写插值查找算法
        public static int insertValueSearch(int[] arr,int left,int right,int value){
    
            if(right<left)
                return -1;
            int mid=left+(right-left)*(value-arr[left])/(arr[right]-arr[left]);
            if(arr[mid]>value){
                return insertValueSearch(arr,left,mid-1,value);
            }
            else if(arr[mid]<value){
                return insertValueSearch(arr,mid+1,right,value);
            }
            else {
                return mid;
            }
    
    
    
    
        }
    }

**几种结果**

>     System.out.println(insertValueSearch(arr, 0, arr.length - 1, 1));  ----0
> 
>     System.out.println(insertValueSearch(arr, 0, arr.length - 1, 5)); -----4
> 
>     System.out.println(insertValueSearch(arr, 0, arr.length - 1, 101)); -----(-1)

3.代码实现(非递归)

public static int insertValueSearch2(int[] arr,int value){
            int left = 0;
            int right = arr.length - 1;
            int mid;
            while (left <= right) {
                mid = left+(right-left)*(arr[right]-value)/(arr[right]-arr[left]);
                if (arr[mid] > value) {//向左找
                    right = mid - 1;
                } else if (arr[mid] < value) {//向右找
                    left = mid + 1;
                } else {
                    return mid;
                }
    
            }
            return -1;
        }

**几种结果**

>     System.out.println(insertValueSearch(arr,1));  ----0
> 
>     System.out.println(insertValueSearch(arr,5)); -----4
> 
>     System.out.println(insertValueSearch(arr,101)); -----(-1)

### 4.注意事项 ###

1)对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找,速度较快.  
2)关键字分布不均匀的情况下，该方法不一定比折半查找要好

## 四.斐波那契查找 ##

### 1.基本介绍 ###

斐波那契数列\{1,2,3,5,8,13,21,34,55\}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618

**原理**

斐波那契查找原理与前两种相似，仅仅改变了中间结点(mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列），如下图所示

![5be2b0ab640d48538586b6a591eb9579.png][]

对F(k-1)-1的理解:  
1)由斐波那契数列F\[K\]=F\[K-1\]+F\[k-2\]的性质，可以得到（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

2)类似的，每一子段也可以用相同的方式分割

3)但顺序表长度n不一定刚好等于F\[K\]-1，所以需要将原来的顺序表长度n增加至F\[K\]-1。这里的k值

只要能使得F\[k\]-1恰好大于或等于n郎可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到FIk\]-1位置），都赋为n位置的值即可。

> while(n>fib(k)-1)  
> k++;

### 2.代码实现(非递归) ###

public class FibonacciSearch {
    
        public static int maxSize=20;
    
        public static void main(String[] args) {
            int[] arr={1,8,10,89,1000,1234};
            System.out.println("查找的index为:"+fibonacciSearch(arr, 12134));
        }
        //因为后面我们mid=low+F(k-1)-1,需要使用到斐波那契数列,因此我们需要先获取到一个斐波那契数列
        public static int[] fibonacci(){
           int[] f= new int[maxSize];
           f[0]=1;
           f[1]=1;
           for(int i=2;i<maxSize;i++){
               f[i]=f[i-1]+f[i-2];
           }
           return f;
    
        }
        public static int fibonacciSearch(int[] arr,int key){
            int low=0;
            int high=arr.length-1;
            int mid;
            int f[]=fibonacci();
            int k=0;  //表示斐波那契数组的下标
            //获取到斐波那契额数列分割数值的下标
            while (high>f[k]-1){
                k++;
            }
            //因为f[k]的值可能大于arr数组的长度,所以我们需要构造一个长度为f[k]的数组,不足的部分用0补齐
            int[] temp = Arrays.copyOf(arr, f[k]);
            //实际上需求使用a数组最后的数填充temp
            for(int i=arr.length;i<temp.length;i++){
                temp[i]=arr[arr.length-1];
            }
    
            //使用while循环处理,找到key
            while(low<=high){
                mid=low+f[k-1]-1;
                if(key<temp[mid]){//向左查找
                  high=mid-1;
                  //通过斐波那契额数组将temp分为两部分,前边部分的长度为f[k-1]-1;
                  //现在需要对前半部分继续查找,因此k--;
                  k--;
                }
                else if(key>temp[mid]){//向右查找
                    low=mid+1;
                    //通过斐波那契额数组将temp分为两部分,前边部分的长度为f[k-2]-1;
                    //现在需要对后半部分继续查找,因此k-=2;
                    k-=2;
                }
                else {//找到了
                    if(mid<arr.length-1)
                        return mid;
                    else
                        return arr.length-1;
                }
    
            }
            return -1;
    
    
    
        }
    }

**几种结果**

>     System.out.println("查找的index为:"+fibonacciSearch(arr, 12134)); ----(-1)
> 
>     System.out.println("查找的index为:"+fibonacciSearch(arr, 1000));  ----4

[e7d2709f9b1e41d6a6af4b368fcaa7b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bdd47c35c49e4251b2791ad847bb3607.png
[5be2b0ab640d48538586b6a591eb9579.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e1cda104c0754e918ef1531a68f9028b.png