经典算法——顺序查找

😁学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰👍 活动地址：CSDN21天学习挑战赛⭐️⭐️⭐️

文章目录

• 顺序查找
• 算法效率
• 实现思路
• 代码实现
• 效率分析
  • 时间复杂度
  • 空间复杂度
• 顺序查找的优缺点

顺序查找

顺序查找也叫线性查找

查找过程：从列表中的第一个元素开始，逐个元素进行比较，如果找到相等的元素，则 查找成功 ，如果直至表中最后一个记录数与目标值都不相等，则表示 查找失败 。 顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。

算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

实现思路

给定一个查找表

在这里插入图片描述

设：查找的目标值为67，步骤如下

1. 从表中的第一个元素开始比较，51 != 67，指针右移

在这里插入图片描述

1. 指针指向第二个元素，也就是4, 4 != 67，指针右移

在这里插入图片描述

1. 指针指向第三个元素，也就是12，12 != 67，指针右移

在这里插入图片描述

1. 指针指向第四个元素，也就是67，67 == 67，查找成功

在这里插入图片描述

代码实现

Java代码实现

定义顺序查找方法

 private int orderFind(int number) {
        //定义一个数组
        int[] arr = {51, 4, 12, 67, 45, 23, 68, 32};

        //定义数组下标
        int i = 0;
        //便利整个数组
        while (i < arr.length) {
            //如果当前元素和number相等，直接返回当前的下标
            if (arr[i] == number) {
                return i;
            }
            //每循环一次，下标+1
            i++;
        }
        //如果最后未找到，那么返回一个标识 -1
        return -1;
    }

调用方法

// 定义要查找的数字
int findNum = 67;
// 顺序查找 67这个数字在数组中的位置
int i = orderFind(findNum);
//如果结果不为-1，那么说明在数组中匹配到了相等的元素
if(i != -1){
    System.out.println("在数组中匹配到数字，下标为：" + i );
}else{
    System.out.println("在数组中未找到");
}

效率分析

时间复杂度

• 最坏的情况

最坏的情况就是完整的遍历了整个集合，也并未找到目标的key，此时循环被完整的执行，循环执行次数与n相关，所以时间复杂度为O(n)。

• 最好的情况

最好的情况就是第一次就找到了元素，此时的时间复杂度为常数级O(1)。

• 平均情况

综合两种情况，顺序查找的时间复杂度为O(n)，属于查找较慢的算法。

空间复杂度

由于算法不会改变原有的元素集合，只需要一个额外的变量控制索引变化，所以空间复杂度为常数级：O(1)

顺序查找的优缺点

1）缺点：查找效率较低，特别是当待查找集合中元素较多时，不推荐使用顺序查找。 2）优点：算法简单而且使用面广。