软考-软件设计师：查找算法-顺序查找（线性查找）

作者：马育民 • • 阅读：10059

介绍

顺序查找，也叫 线性查找，将待查找的元素 key，与表中第一个元素进行比较，一个一个往后比对，如果存在 key ，则返回查找成功；否则，返回查找失败。

查找步骤

  1. 遍历待查找的数组/列表，从索引 0（第一个元素）开始；
  2. 每遍历一个元素，就和目标值做比较；
  3. 若相等，返回该元素的索引（表示找到）；
  4. 若遍历完所有元素仍未找到，返回一个特殊值（如-1）表示查找失败。

适用场景

线性查找适合小数据量（且无序）的查找场景，比如列表长度小于100；

如果是大数据量（万级/百万级） 且数据有序，建议使用二分查找（效率远高于线性查找）；

例子

给定一个无序的数字序列：[7, 2, 9, 4, 1, 8]，要找数字 4，用顺序查找的步骤：

  1. 检查第 1 个数字 7 → 不是 4，继续；
  2. 检查第 2 个数字 2 → 不是 4，继续；
  3. 检查第 3 个数字 9 → 不是 4，继续；
  4. 检查第 4 个数字 4 → 找到目标，停止查找。

如果要找数字 5，就会依次检查完 6 个数字（7→2→9→4→1→8），最终确定序列里 没有 5

优缺点

优点

  1. 实现简单：无需复杂逻辑，新手易理解、易编写；
  2. 无数据要求：待查找的列表 无需排序，有序/无序都能查；
  3. 数据结构友好：适配数组、链表等几乎所有线性数据结构；
  4. 支持提前终止：找到目标值后立即返回，无需遍历全部元素。

缺点

  • 效率较低：最坏情况下需要遍历全部元素（目标值在最后/不存在），时间复杂度高。

查找速度

最好情况

O(1)，目标值是列表第一个元素，一次比较就找到；

最坏情况

O(n)，n是列表长度，目标值在最后/不存在，需要n次比较；

平均情况

推导过程：

  • 目标在第 1 位：需要 1 次比较
  • 目标在第 2 位：需要 2 次比较
  • …
  • 目标在第n位：需要 n 次比较，概率n

\frac{1 + 2 + 3 + \ldots + n } { n}

提示： 除以 n 是因为计算平均情况

因为 1 + 2 + 3 + \ldots + n = n*(1+n)/2 ，所以

\frac{(1 + n ) * n} { 2 * n}

约掉n，最后结果：

\frac{ 1 + n} {2}

时间复杂度

最好情况

O(1)，目标值是列表第一个元素，一次比较就找到；

最坏情况

O(n)，n是列表长度，目标值在最后/不存在，需要n次比较；

平均情况

由 查找速度-平均情况可知，平均情况是： \frac{ 1 + n} {2}

用 大O表示法，也就是：O(n)

空间复杂度

O(1)，仅使用了少量临时变量（索引、目标值），无需额外开辟内存空间，属于原地查找。

实现

java

public class LinearSearchBasic {
    public static int linearSearch(int[] arr, int target) {
        // 判空，避免空指针异常（工程开发必备）
        if (arr == null) {
            return -1;
        }
        int n = arr.length; // 提取数组长度，避免多次调用arr.length
        // 从索引0遍历到n-1
        for (int i = 0; i < n; i++) {
            if (arr[i] == target) {
                return i;  // 找到目标，立即返回索引（提前终止）
            }
        }
        return -1;
    }

    // 测试
    public static void main(String[] args) {
        // 测试用例1：包含目标值
        int[] numArr1 = {5, 2, 9, 1, 5, 6};
        int target1 = 9;
        System.out.println("目标值" + target1 + "的索引：" + linearSearch(numArr1, target1)); // 输出：2

        // 测试用例2：不包含目标值
        int target2 = 3;
        System.out.println("目标值" + target2 + "的索引：" + linearSearch(numArr1, target2)); // 输出：-1

        // 测试用例3：空数组
        int[] numArr2 = {};
        System.out.println("空数组查找结果：" + linearSearch(numArr2, 5)); // 输出：-1
    }
}

python

# 线性查找核心函数
# 参数：arr-待查找的列表，target-要找的目标值
# 返回：找到则返回目标值的索引，未找到返回-1
def linear_search_basic(arr, target):
    n = len(arr)  # 获取列表长度
    for i in range(n):  # 从索引0遍历到n-1
        if arr[i] == target:  # 找到目标值，立即返回索引
            return i
    return -1  # 遍历结束未找到，返回-1

# 测试代码
if __name__ == "__main__":
    # 测试用例1：数字列表（包含目标值）
    num_list = [5, 2, 9, 1, 5, 6]
    target1 = 9
    print(f"目标值{target1}的索引：{linear_search(num_list, target1)}")  # 输出：2

    # 测试用例2：数字列表（不包含目标值）
    target2 = 3
    print(f"目标值{target2}的索引：{linear_search(num_list, target2)}")  # 输出：-1

    # 测试用例3：字符串列表
    str_list = ["Python", "Java", "C", "JavaScript"]
    target3 = "C"
    print(f"目标值{target3}的索引：{linear_search(str_list, target3)}")  # 输出：2

原文出处：/show_1GWvXgK6yi8.html

吉ICP备15003043号