数据结构与算法查找算法

JAY.LIN 收录于数据结构与算法

2021-12-05 约 1891 字预计阅读 4 分钟

https://bing.ee123.net/img/rand?artid=121725646

数据结构与算法——查找算法

一、查找算法

1.1 分类

线性查找
二分查找
插值查找
斐波那契查找

二、线性查找（SequenceSearch）

2.1 基本思想

逐一比对待排序序列，找出待查找元素的下标。

2.2 线性查找算法实现

代码：

public class SequenceSearch {
    public static void main(String[] args) {
        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, -1};
        int index = search(arr, 2);
        if (index == -1) {
            System.out.println("序列中不存在该元素。");
        } else {
            System.out.println("该元素下标为：" + index);
        }
    }

    public static int search(int[] arr, int value) {
        //逐一比对待排序序列
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

结果：

三、二分查找（BinarySearch）

3.1 基本思想

先确定有序序列的中间下标，然后向左右两边递归进行二分查找，直到中间下标为待查找元素的下标。

3.2 二分查找算法实现

代码：

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {-1, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int index = search(arr, 0, arr.length - 1, 5);
        if (index == -1) {
            System.out.println("序列中不存在该元素。");
        } else {
            System.out.println("该元素下标为：" + index);
        }
    }

    public static int search(int[] arr, int startIndex, int endIndex, int value) {
        if (startIndex > endIndex || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        //定义中间元素下标
        int mid = (startIndex + endIndex) / 2;
        //定义中间元素值
        int midVal = arr[mid];

        if (value > midVal) {
            //向右递归
            return search(arr, mid + 1, endIndex, value);
        } else if (value < midVal) {
            //向左递归
            return search(arr, startIndex, mid - 1, value);
        } else {
            return mid;
        }
    }
}

结果：

四、插值查找（InterpolationSearch）

4.1 基本思想

类似于二分查找，但改变了每次查找的期望索引值。

4.2 期望索引值公式

Expectation = startIndex + (endIndex - startIndex) * (value - arr[startIndex]) / (arr[endIndex] - arr[startIndex])

4.3 插值查找算法实现

代码：

public class InterpolationSearch {
    public static void main(String[] args) {
        int arr[] = {-1, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int index = search(arr, 0, arr.length - 1, 5);
        if (index == -1) {
            System.out.println("序列中不存在该元素。");
        } else {
            System.out.println("该元素下标为：" + index);
        }
    }

    public static int search(int[] arr, int startIndex, int endIndex, int value) {
        if (startIndex > endIndex || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        //定义期望元素下标
        int expectation = startIndex + (endIndex - startIndex) * (value - arr[startIndex]) / (arr[endIndex] - arr[startIndex]);
        //定义期望元素值
        int expectationVal = arr[expectation];

        if (value > expectationVal) {
            //向右递归
            return search(arr, expectationVal + 1, endIndex, value);
        } else if (value < expectationVal) {
            //向左递归
            return search(arr, startIndex, expectationVal - 1, value);
        } else {
            return expectationVal;
        }
    }
}

结果：

五、斐波那契查找（FibonacciSearch）

5.1 基本介绍

斐波那契查找算法又称黄金分割查找算法，黄金分割点是指把一条线段分割成两部分，使其中一部分与全长之比等于另一部分与该部分之比，该比值的近似值为0.618。

相邻两个元素之比无限接近黄金分割值的数列被称为斐波那契数列。

5.2 基本思想

类似于二分查找，但改变了每次查找的期望索引值，该期望索引值位于黄金分割点附近。

5.3 期望索引值公式

Expectation = startIndex + F(k - 1) - 1，F表示斐波那契数列。

由斐波那契数列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的两部分，期望索引值的下标为startIndex + F(k - 1) - 1。
当有序序列的长度不为F(k) - 1时，需要将该序列的长度增加至F(k) - 1。

5.4 斐波那契查找算法实现

代码：

public class FibonacciSearch {

    //定义斐波那契数列的长度
    public static int maxSize = 20;

    public static void main(String[] args) {
        int arr[] = {-1, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int index = search(arr, 5);
        if (index == -1) {
            System.out.println("序列中不存在该元素。");
        } else {
            System.out.println("该元素下标为：" + index);
        }
    }

    public static int search(int[] arr, int value) {
        //定义头指针
        int startIndex = 0;
        //定义尾指针
        int endIndex = arr.length - 1;
        //定义期望元素下标
        int expectation = 0;
        //定义斐波那契分割数值的下标
        int k = 0;
        //定义斐波那契数列
        int[] f = fibonacci();
        //获取斐波那契分割数值
        while (endIndex > f[k] - 1) {
            k++;
        }
        //有序序列长度不足时增加其长度，存入临时数组中，不足部分使用arr数组末尾的值进行填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = endIndex + 1; i < temp.length; i++) {
            temp[i] = arr[endIndex];
        }

        while (startIndex <= endIndex) {
            expectation = startIndex + f[k - 1] - 1;
            //定义期望元素值
            int expectationVal = arr[expectation];

            if (value > expectationVal) {
                //向右查找
                startIndex = expectation + 1;
                //右边的有序序列有f[k-2]个元素，可拆分成f[k-2]=f[k-3]+f[k-4]，k-2作为新的斐波那契分割数值的下标
                k -= 2;
            } else if (value < expectationVal) {
                //向左查找
                endIndex = expectation - 1;
                //左边的有序序列有f[k-1]个元素，可拆分成f[k-1]=f[k-2]+f[k-3]，k-1作为新的斐波那契分割数值的下标
                k--;
            } else {
                //判断查找到的元素下标是否位于增加出的部分，是则返回数组末尾下标
                if (expectation <= endIndex) {
                    return expectation;
                } else {
                    return endIndex;
                }
            }
        }
        return -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;
    }
}

结果：