顺序查找算法图文详解

顺序查找（又称顺序搜索、线性搜索等）是所有查找算法中最基本、最简单的一种算法，该算法的时间复杂度为O(n)。

顺序查找算法既支持在有序序列中查找目标元素，也支持在无序序列中查找目标元素，该算法的核心思想是：遍历整个数据集，检查每个元素是否为要找的目标元素，如果是则返回该元素所处的位置，反之则继续遍历。直至序列中最后一个元素，如果仍未查找成功，则表明序列中没有目标元素。

例如，用顺序查找算法在{10,14,19,26,27,31,33,35,42,44}序列中查找目标元素 33，如下动画演示了整个查找过程：

图 1 顺序查找算法

也就是说，顺序查找算法会遍历整个目标序列，每找到一个元素，都会和目标元素进行比对，直至找到目标元素或者遍历完整个目标序列（查找失败）。

如下为实现顺序查找算法的伪代码：

输入 arr[]                                // 输入要查找的数据集
linear_search(arr , value):       // value 表示要查找的目标元素
    for i <-1 to length(arr):      // 从 arr 序列中第一个元素开始遍历，直至最后一个元素
        if arr[i] == value:           // 如果成功找到一个元素和目标元素匹配，则返回该元素所处的位置
            return i                     
    return -1                            // 返回 -1，表示查找失败。

顺序查找算法的具体实现

如下为实现顺序查找算法的 C 语言程序：

#include <stdio.h>
#define N 10     //数据集中的元素个数
//实现顺序查找，arr[N] 为数据集，value 为要查找的目标元素
int linear_search(int arr[N], int value) {
    int i;
    //从第 1 个元素开始遍历
    for (i = 0; i < N; i++) {
        //匹配成功，返回元素所处的位置下标
        if (arr[i] == value) {
            return i;
        }
    }
    //匹配失败，返回 -1
    return -1;
}

int main()
{
    int arr[N] = { 10,14,19,26,27,31,33,35,42,44 };
    int add = linear_search(arr, 33);
    if (add != -1) {
        printf("查找成功，为序列中第 %d 个元素", add + 1);
    }
    else {
        printf("查找失败");
    }
    return 0;
}

如下为实现顺序查找算法的 Java 程序：

public class Demo {
    // 实现顺序查找，arr[N] 为数据集，value 为要查找的目标元素
    public static int linear_search(int[] arr, int value) {
        // 从第 1 个元素开始遍历
        for (int i = 0; i < arr.length; i++) {
            // 匹配成功，返回元素所处的位置下标
            if (arr[i] == value) {
                return i;
            }
        }
        // 匹配失败，返回 -1
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
        int add = linear_search(arr, 33);
        if (add != -1) {
            System.out.println("查找成功，为序列中第 " + (add + 1) + " 个元素");
        } else {
            System.out.println("查找失败");
        }
    }
}

如下为实现顺序查找算法的 Python 程序：

格式化复制

arr = [10,14,19,26,27,31,33,35,42,44]
def linear_search(value):
    for i in range(len(arr)):
        if arr[i] == value:
            return i
    return -1

add = linear_search(33)
if add != -1:
    print("查找成功，为序列中第 %d 个元素" % (add + 1))
else:
    print("查找失败")

以上程序的输出结果均为：

查找成功，为序列中第 7 个元素