博客

详解顺序查找算法原理与使用方法

顺序查找算法

什么是顺序查找算法

顺序查找算法是一种最基础、最简单的查找算法，也被称为线性查找算法，其本质是在一个数据集中顺序查找目标值，以确定目标值在序列中是否存在。

顺序查找算法如何实现

顺序查找算法的实现非常简单，步骤如下：

  1. 从序列的第一个元素开始遍历，逐个和目标值进行比较
  2. 如果找到目标值，返回该元素在序列中的下标
  3. 如果遍历完整个序列依然没有找到目标值，返回-1或者抛出异常等标识未找到

示例代码如下：

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

顺序查找算法的优缺点

优点

  • 算法简单易理解易实现
  • 数据集的存储方式可以是数组、链表、文本等任意可线性访问的数据结构，因此适用范围广泛
  • 对于数据集比较小的情况表现较好

缺点

  • 在数据集比较大时，效率低下，时间复杂度为O(n)
  • 无法利用数据集的任何特殊结构或者有序性

顺序查找算法的使用方法

顺序查找算法可以应用于各种数据集合的查找，包括但不限于数组、链表、文本等。下面介绍使用顺序查找算法解决两个问题的示例。

示例一：从一个整数数组中查找某个整数是否存在

例如，给定一个有序整数数组[1, 5, 9, 11, 15, 19, 22, 25]，我们需要查找数字11是否在其中。可以用如下代码实现：

arr = [1, 5, 9, 11, 15, 19, 22, 25]
target = 11

index = sequential_search(arr, target)

if index == -1:
    print("Target is not found")
else:
    print("Target is at index: ", index)

输出结果：

Target is at index: 3

示例二：从一个文本文件中查找某个字符串是否存在

例如，现在有一个文本文件test.txt，内容如下：

This is a test file for sequential search algorithm.
Sequential search is very simple but may not be very efficient.

我们需要查找文本中是否包含字符串”search”。可以用如下代码实现：

with open("test.txt", "r") as f:
    lines = f.readlines()

target = "search"

for i in range(len(lines)):
    if target in lines[i]:
        print("Target is found in line: ", i+1)
        break
else:
    print("Target is not found in the file")

输出结果：

Target is found in line:  1
Tags: