欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

常见查找算法

程序员文章站 2022-03-05 16:17:30
...

常见查找算法

本篇介绍了几种常见的查找算法：顺序查找、二分查找、插值查找、斐波那契查找、二叉树查找

准备工作

public class SearchDemo {

    /** 普通无序数组 */
    private int[] normalArr = new int[20];
    /** 有序递增数组 */
    private int[] sortedlArr = new int[20];
    /** num1：无序算法要查找的整数；num2：有序算法要查找的整数；index：找到的数在对应数组中的索引，没有则为-1 */
    private int num1, num2, index = -1;

    @BeforeEach
    public void before() {
        Random random = new Random();
        for (int i = 0; i < normalArr.length; i++) {
            normalArr[i] = random.nextInt(1000);
        }
        // 增数列
        int num = 0;
        for (int i = 0; i < sortedlArr.length; i++) {
            sortedlArr[i] = (num += random.nextInt(30));
        }
        num1 = normalArr[random.nextInt(20)];
        num2 = sortedlArr[random.nextInt(20)];
    }

顺序查找

顾名思义，遍历数组中元素，直到找到匹配的为止，数组是否有序不影响该算法

优点：

对数组无要求，可以对无序数组中进行查找

缺点：

时间复杂度高，不适宜在大量数据中查找

/**
 * 顺序查找
 */
@Test
public void sequentialSearch() {
    if (normalArr.length <= 0) {
        return;
    }
    if (normalArr.length == 1) {
        index = normalArr[0] == num1 ? 0 : -1;
        return;
    }
    for (int i = 0; i < normalArr.length; i++) {
        if (normalArr[i] == num1) {
            index = i;
            break;
        }
    }
    System.out.println("normalArr: " + Arrays.toString(normalArr));
    if (index == -1) {
        System.out.println("num=" + num1);
        System.out.println("数组中没有该数字");
    } else {
        System.out.println("num=" + num1);
        System.out.println("normalArr[" + index + "]=" + normalArr[index]);
        System.out.println("验证" + (num1 == normalArr[index] ? "" : "不") + "通过");
    }
}

结果如下：

normalArr: [791, 108, 892, 759, 945, 446, 976, 524, 536, 909, 691, 899, 417, 801, 733, 237, 601, 552, 929, 48]

num=791

normalArr[0]=791

验证通过

二分查找

每次从数组的动态范围（第一次是整个数组）内取中间位置的数比较，将要查找的数锁定在两个更小的范围之一，逐步缩小范围，直到查找到对应的数或者算法结束

优点：查询速度快

缺点：要求数组有序

二分查找适宜于基本没有数据变动且查找操作频繁的有序数组

/**
 * 二分查找
 */
@Test
public void binarySearch() {
    if (sortedlArr.length <= 0) {
        return;
    }
    if (sortedlArr.length == 1) {
        index = sortedlArr[0] == num2 ? 0 : -1;
        return;
    }
    if (num2 < sortedlArr[0] || num2 > sortedlArr[sortedlArr.length - 1]) {
        return;
    }
    int start = 0;
    int end = sortedlArr.length - 1;
    while (start <= end) {
        if (start == end) {
            if (sortedlArr[start] == num2) {
                index = start;
            }
            break;
        }
        int mid = (start + end) / 2;
        int midNum = sortedlArr[mid];
        if (midNum == num2) {
            index = mid;
            break;
        }
        if (midNum > num2) {// (start, mid)
            end = mid - 1;
        }
        if (midNum < num2) {// (mid, end)
            start = mid + 1;
        }
    }
    System.out.println("sortedlArr: " + Arrays.toString(sortedlArr));
    if (index == -1) {
        System.out.println("num=" + num2);
        System.out.println("数组中没有该数字");
    } else {
        System.out.println("num=" + num2);
        System.out.println("sortedlArr[" + index + "]=" + sortedlArr[index]);
        System.out.println("验证" + (num2 == sortedlArr[index] ? "" : "不") + "通过");
    }
}

结果如下：

sortedlArr: [16, 32, 43, 49, 58, 73, 90, 119, 122, 130, 147, 149, 175, 179, 199, 214, 221, 229, 234, 254]

num=234

sortedlArr[18]=234

验证通过

插值查找

插值查找是对二分查找的改进，改进之处在对mid即判断的数的位置的取值方法上，二分法是直接去中间位置，而插值查找则向着离查找的数更近似的方式去取数组中的判断数的位置使得每一次取数离查找目标更近，从而更快的找到目标数字

优点：

查询速度快

对于关键字分布均匀的数组来说，查询速度将优于折半查找。如果关键字分布不均匀，则查询速度与折半查找速度近似

缺点：

与二分查找一样，要求数组有序

插值查找适宜于基本没有数据变动且查找操作频繁的有序数组

/**
 * 插值查找
 */
@Test
public void insertSearch() {
    if (sortedlArr.length <= 0) {
        return;
    }
    if (sortedlArr.length == 1) {
        index = sortedlArr[0] == num2 ? 0 : -1;
        return;
    }
    if (num2 < sortedlArr[0] || num2 > sortedlArr[sortedlArr.length - 1]) {
        return;
    }
    int low = 0;
    int high = sortedlArr.length - 1;
    int mid;
    while (low <= high) {
        if (low == high) {
            if (num2 == sortedlArr[low]) {
                index = low;
            }
            break;
        }
        int highValue = sortedlArr[high];
        int lowValue = sortedlArr[low];
        mid = low + (num2 - lowValue) / (highValue - lowValue) * (high - low);
        if (num2 == sortedlArr[mid]) {
            index = mid;
            break;
        }
        if (num2 > sortedlArr[mid]) {
            low = mid + 1;
        }
        if (num2 < sortedlArr[mid]) {
            high = mid - 1;
        }
    }
    System.out.println("sortedlArr: " + Arrays.toString(sortedlArr));
    if (index == -1) {
        System.out.println("num=" + num2);
        System.out.println("数组中没有该数字");
    } else {
        System.out.println("num=" + num2);
        System.out.println("sortedlArr[" + index + "]=" + sortedlArr[index]);
        System.out.println("验证" + (num2 == sortedlArr[index] ? "" : "不") + "通过");
    }
}

结果如下：

sortedlArr: [1, 2, 22, 25, 38, 40, 44, 53, 70, 80, 99, 122, 148, 155, 170, 188, 204, 223, 250, 250]

num=80

sortedlArr[9]=80

验证通过

斐波那契查找

也是对二分查找的改进，斐波那契数列的定义是F(k)=1, k∈[1, 2]或F(k)=F(k-1)+F(k-2), k≥3，而k趋向于正无穷时，F(k)/F(k-1)≈F(k-1)/F(k-2)=0.618，即黄金分割比例，通过将中间取数改进为按照黄金分割比例取数，提高查找效率，算法思路在如下的方法注释中

优点：

查询速度快

相比于插值查找，斐波那契查找不受数值影响

查询速度优于二分查找

缺点：

要求数组有序

该算法可能会调整原数组长度，即需要在数组后边以最后一个值填充，不论是使用辅助函数还是构建新数组，会消耗空间资源

斐波那契查找适宜于基本没有数据变动且查找操作频繁的有序数组

/**
 * 斐波那契查找
 *
 * n表示数组长度
 * F(k)表示斐波那契数列
 *
 * 令 F(k)-1=n
 * 而F(k) = F(k-1)+F(k-2)
 * 所以 F(k-1)+F(k-2)-1=n
 *
 * 原来的二分查找的mid
 * mid=low+(low+high)/2
 *
 * 因为拿的是F(k-1)比较，而F(k-1)>=F(k-2)，所以mid的位置在数组中间偏右边，即右边的黄金分割点
 * 所以新的mid这样算
 * mid=low+F(k-1)-1，减1防止索引溢出，参考k=2的情况
 *
 * 判断的情况分三种讨论:
 *
 * =：mid即查找值
 *
 * >：查找值在mid右边，所以low=mid+1，即查找值在范围[mid+1, high]中，而high=n-1，mid+1=low+F(k-1)，
 * 元素个数为：(n-1)-(low+F(k-1))+1=n-low-F(k-1)=F(k)-1-low-F(k-1)=F(k-2)-1-low
 * 即查找值在黄金分割中较小的范围内，所以k要自减2
 *
 * <：查找值在mid左边，所以high=mid-1，即查找值在范围[low, mid-1]中，而low=0，mid-1 = low+F(k-1)-2，
 * 元素个数为：low+F(k-1)-2-low+1=low+F(k-1)-1
 * 即查找值在黄金分割中较大的范围内，所以k自减1
 */
@Test
public void fibonacciSearch() {
    if (sortedlArr.length <= 0) {
        return;
    }
    if (sortedlArr.length == 1) {
        index = sortedlArr[0] == num2 ? 0 : -1;
        return;
    }
    int len = sortedlArr.length;// 数组长度
    Integer[] fibonacciArr = getFibonacciArray(len);// 获取相应的斐波那契数列
    int fibonacciArrHighValue = fibonacciArr[fibonacciArr.length - 1];// 获取斐波那契数列中最后一个，即最大的数
    int highValue = sortedlArr[sortedlArr.length - 1];// 获取有序数组中最大的数
    // 有序数组作填充处理
    int[] tmp = null;
    if (fibonacciArrHighValue - 1 > len) {
        int[] _tmp = new int[fibonacciArrHighValue - 1];
        System.arraycopy(sortedlArr, 0, _tmp, 0, len);
        Arrays.fill(_tmp, len, _tmp.length, highValue);
        tmp = sortedlArr;
        sortedlArr = _tmp;
    }
    int low = 0, high = sortedlArr.length - 1;
    int k = fibonacciArr.length - 2;
    int mid;
    while (k >= 0) {
        mid = low + fibonacciArr[k] - 1;
        if (sortedlArr[mid] == num2) {
            index = mid;
            break;
        } else if (num2 > sortedlArr[mid]) {
            low = mid + 1;
            k = k - 2;
        } else {
            high = mid - 1;
            k--;
        }
    }
    // 有序数组还原
    if (sortedlArr.length != len) {
        sortedlArr = tmp;
    }
    System.out.println("sortedlArr: " + Arrays.toString(sortedlArr));
    if (index == -1) {
        System.out.println("num=" + num2);
        System.out.println("数组中没有该数字");
    } else {
        System.out.println("num=" + num2);
        System.out.println("sortedlArr[" + (index >= len ? len - 1 : index) + "]=" + sortedlArr[index]);
        System.out.println("验证" + (num2 == sortedlArr[index] ? "" : "不") + "通过");
    }
}



/**
 * 根据数组的长度获取对应的斐波那契数列
 *
 * @param len 数列长度
 * @return
 */
private Integer[] getFibonacciArray(int len) {
    List<Integer> list = new ArrayList<>();
    if (len > 0) {
        int i = 0;
        int a = 0, b = 0, num = 0;
        while (true) {
            if (i == 0) {
                a = 1;
                list.add(a);
                num = 1;
            } else if (i == 1) {
                b = 1;
                list.add(b);
                num = 1;
            } else {
                num = a + b;
                list.add(num);
                a = b;
                b = num;
            }
            if (num - 1 >= len) {
                break;
            }
            i++;
        }
    }
    Integer[] array = list.toArray(new Integer[list.size()]);
    return array;
}

结果如下：

sortedlArr: [2, 15, 27, 47, 47, 49, 49, 66, 70, 72, 94, 95, 97, 98, 127, 142, 161, 176, 180, 190]

num=66

sortedlArr[7]=66

验证通过

二叉树查找

主要利用了二叉排序树的性质，对于一个二叉排序树中的任意节点，其左子节点（存在时）小于该节点的值，其右子节点（存在时）大于该节点的值，即对二叉排序树中序遍历，可得到有序数列

优点：

可排序无序数组

插入和查找的效率都快

缺点：

需要额外空间（构建二叉树结构）

当查找的原数组有序时，不适宜用二叉树查找，此时二叉树查找等同于顺序查找（除非在插入时对二叉树结构进行优化）

本例中采用先序遍历进行查找

/**
 * 二叉树查找
 */
@Test
public void binaryTreeSearch() {
    SortedBinaryTree tree = new SortedBinaryTree(normalArr);
    index = tree.indexOf(num1);
    System.out.println("normalArr: " + Arrays.toString(normalArr));
    if (index == -1) {
        System.out.println("num=" + num1);
        System.out.println("数组中没有该数字");
    } else {
        System.out.println("num=" + num1);
        System.out.println("normalArr[" + index + "]=" + normalArr[index]);
        System.out.println("验证" + (num1 == normalArr[index] ? "" : "不") + "通过");
    }
}

/**
 * 二叉排序树
 * 二叉排序树是二叉树的一种，对于二叉排序树而言，若
 * 一个节点有左或右子节点，则始终存在左节点的值不小于（或不大于）
 * 父节点，右节点的值不大于（或不小于）父节点，即对二叉排序树
 * 进行中序遍历，得到的数列是有序的
 */
@Getter
@Setter
private static class SortedBinaryTree {

    private Node head;// 头节点
    private Integer min;// 二叉树中最小值
    private Integer max;// 二叉树中最大值
    private Integer currentIndex;

    public SortedBinaryTree(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            add(arr[i]);
        }
    }

    /**
     * 按照中序遍历从小到大的方式对新增节点作处理
     * 等值放在左子节点，或者不加也可以
     * 思路：
     * @param num
     */
    public void add(int num) {
        if (null == head) {
            currentIndex = 0;
            head = new Node(num, currentIndex);
            min = max = num;
            return;
        }
        Node node;
        node = head;
        while (true) {
            if (num > node.num) {// 该值比当前节点的值大，放到该节点的右子树上
                if (null == node.right) {
                    node.right = new Node(num, ++currentIndex);
                    break;
                }
                node = node.right;
            } else {// 该值不大于当前节点的值，放到该节点的左子树上
                if (null == node.left) {
                    node.left = new Node(num, ++currentIndex);
                    break;
                }
                node = node.left;
            }
        }
        min = min > num ? num : min;
        max = max < num ? num : max;
    }

    /**
     * 返回其在数组中的索引
     * @param num
     * @return
     */
    public int indexOf(int num) {
        if (num >= min && num <= max) {
            Node node = head;
            while (null != node) {
                if (num == node.num) {
                    return node.index;
                } else if (num > node.num) {
                    node = node.right;
                } else {
                    node = node.left;
                }
            }
        }
        return -1;
    }

    /**
     * 树的节点模型
     */
    private class Node {
        private int num;
        private int index;// 在数组中的索引
        private Node left;// 左子节点
        private Node right;// 右子节点

        public Node(int num, int index) {
            this.num = num;
            this.index = index;
        }
    }
}

结果如下：

normalArr: [444, 504, 431, 389, 988, 326, 356, 918, 681, 624, 538, 419, 917, 527, 977, 680, 865, 853, 132, 602]

num=624

normalArr[9]=624

验证通过

 

相关标签： 算法 查找

上一篇： 深入浅出Maven：创建普通及Web项目、使用Profile进行资源过滤

下一篇： Intel傲腾905P固盘新增1.5TB、消费级TLC新品700p同时现身

推荐阅读