阅读:0       作者:严长生

顺序查找算法(原理、实现及时间复杂度)

一提到查找,比如从一个数列中查找第1个值为k的数,那么我们最先想到的肯定是一个一个地找。从数列的第 1 个数开始对比,直到找到值为k的数。

顺序查找的定义为:在一个已知无序(或有序)的队列中找出与给定的关键字相同的数的具体位置。其原理是让关键字与队列中的数从开始一个一个地往后逐个比较,直到找到与给定的关键字相同的数。

当然,顺序查找绝不仅限于对数字、字符的查找,也适用于前缀、对象信息的关键信息的匹配等。

顺序查找的原理与实现

顺序查找对数列是否有序没有要求,也就是说是否有序对查找性能来说无关紧要。一般是从数列的一端开始查找,找到则返回对应的元素,没有找到则返回一个无意义的结果。

算法非常简单,我们来看看代码实现:
public class SequentialSearch {
    private int[] array;
    public SequentialSearch(int[] array) {
        this.array = array;
    }
   
    /**
     * 直接顺序查找
     * @param key
     * @return
     */
    public int search(int key) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
其实这个简单的算法也有可优化的地方,优化方法就是把k的值放在数组中下标为 0 的元素上,然后从后往前比较,直到 k 与数组中的某个值相等,这时结束;如果数组中没有与其相等的值,则也会与数组下标为 0 的值相等,这时结束。这样可以避免对于数组越界的比较。

优化后的代码如下:
/**
* 哨兵方式顺序查找
* @param key
* @return
*/
public int search2(int key) {
    // 先判断是否等于下标为0的元素
    if (key == array[0]) {
        return 0;
    }
    // 临时保存array[0]的值
    int temp = array[0];
    // 赋值给下标为0的元素
    array[0] = key;
    int i = array.length - 1;
    // 倒序比较
    while(array[i] != key) {
        i --;
    }
    // 把array[0]原本的值赋回去
    array[0] = temp;
    // 比较到最后了也没有找到返回-1
    if (i == 0) {
        return -1;
    }
    // 找到了的话返回数组下标
    return i;
}
这样,循环部分的比较操作与之前相比少了一半。

顺序查找的特点及性能分析

顺序查找没有难度和技术含量,是我们谁都能想到并且最先会想到一种最直接的方法。比如在玩扑克牌的时候,若不需要大小王,则我们会拿过来所有的牌,从头到尾地一张一张地找。

当然,顺序查找也可以结合并发来处理,比如我们把待查找的数列分为前后两个部分,开启两个线程去查找,这就是利用了多核CPU去更快地完成任务。在上面扑克牌的例子中,我们如果有两个人,就会把牌的一半分给另一个人来一起找,这样显然会更快一些。

在介绍查找算法的性能之前,让我们先来了解一个词 ASL(Average Search Length,平均查找长度)。需要和要查找的 key 进行比较的期望次数,被称为查找算法的平均查找长度。查找成功时的 ASL 的计算公式为 ASL=Pi×Ci,其中,Pi 为查找表中第 i 个元素的概率,Ci 为找到第 i 个元素时已经比较过的次数。

其实我们在很多时候没必要太过纠结上面的公式,ASL 只是辅助我们了解查找性能的,其实和时间复杂度类似。针对顺序查找,在能够找到的情况下,ASL 为 1/n×(1+2+3+…+n),也就是 (1+n)/2,这里假设每个元素的查找概率相等。在最坏的情况下就是没有找到,近似比较 n+2 次(在我们的优化版里需要比较 n+2 次,在普通版顺序查找里则需要比较 2n 次)。

现在我们来看看顺序查找的性能,平均时间复杂度为 O(n),n 是待查数列的长度,这其实没什么好解释的,因为顺序查找是从头到尾查找,而且我们可以看到查找了整个数组。当然最好的情况是数组的第 1 个元素就是我们要找的元素,这样可以直接找到,最坏的情况是到最后一个元素时才找到或者没有找到要找的元素。

这里我们额外分析一种并发查找的情况,实际上我们在并发查找时查找的元素可能更多,比如两个线程把待查数列分成两部分进行查找,如果元素恰巧在第 1 个线程要查的列中,那么第 2 个线程的查找就白做了。但是通常并发还是能够更快地查找的,除了这里提到的特殊情况,元素如果在后面的线程中,则会快很多,尤其是在大数列、更多的线程时。

顺序查找是对数列顺序的比较,没有额外的空间,所以空间复杂度为常数 O(1)

顺序查找的适用场景

顺序查找就是这么简单,以至于我们在一般的简单场景下根本不想用那些复杂的查找算法。

我们有时需要显示一些人的详细信息,比如榜单,我们往往在排行榜中只保存了用户id与得分数,这时可以根据得分数获取前 10 名用于展示,可是我们不知道这些 id 对应哪个人,所以往往还需要用户的一些其他信息如昵称、头像等。

这时我设计了这样一段代码逻辑:先找出前 10 名的 id,再查出这 10 个人的详细信息列表,然后循环这 10 个人的 id,内层循环这 10 个人的详细信息,发现 id 一致时,我们就可以找到对应的某个人的详细信息了。这里就是典型的顺序查找。

顺序查找由于其简单的特点,在元素并不多的很多情况下,运用还是很广泛的。因为没有必要为了有限数量的元素使用复杂的算法。