顺序查找算法

顺序查找算法又称顺序搜索算法或者线性搜索算法，是所有查找算法中最基本、最简单的，对应的时间复杂度为O(n)。

顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。

顺序查找算法的实现思路

所谓顺序查找，指的是从待查找序列中的第一个元素开始，查看各个元素是否为要找的目标元素。

举个简单的例子，采用顺序查找算法在 {10,14,19,26,27,31,33,35,42,44} 序列中查找 33，整个查找过程如下图所示：

图 1 顺序查找 33 的过程

结合图 1，顺序查找算法会遍历整个待查找序列，序列中的每个元素都会和目标元素进行比对，直至找到 33。如果遍历完整个序列仍没有找到与 33 相等的元素，表明序列中不包含目标元素，查找失败。

如下用伪代码给大家展示了顺序查找算法的实现思路：

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

某些场景中，待查找序列可能包含多个目标元素，需要我们全部找到。这种情况下，顺序查找算法仍然适用，只需对实现过程做一下微调即可，对应的伪代码如下：
arr[1…N] //待查找序列 index[1…N] //存储目标元素的位置 j <- 1
linear_search(arr , value): // value 表示要查找的目标元素
for i <-1 to length(arr): // 从 arr 序列中第一个元素开始遍历，直至最后一个元素
if arr[i] == value: // 如果成功找到一个元素和目标元素匹配，则返回该元素所处的位置
index[j] <- i // 将目标元素所在序列的位置存储到 index 中
j <- j + 1 // j 自加，为下次在 index 中存储目标元素的位置做准备
return index

顺序查找算法的具体实现

结合伪代码，如下是使用顺序查找算法在 {10,14,19,26,27,31,33,35,42,44} 中查找 33 的 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;}}//匹配失败，返回 -1return -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;
}

如下是使用顺序查找算法在 {10,14,19,26,27,31,33,35,42,44} 中查找 33 的 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;}}// 匹配失败，返回 -1return -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("查找失败");}}
}

如下是使用顺序查找算法在 {10,14,19,26,27,31,33,35,42,44} 中查找 33 的 Python 程序：

#待查找序列
arr = [10,14,19,26,27,31,33,35,42,44]
#实现顺序查找算法，value 为要查找的目标元素
def linear_search(value):#遍历整个序列for i in range(len(arr)):if arr[i] == value:return ireturn -1
add = linear_search(33)
if add != -1:print("查找成功，为序列中第 %d 个元素" % (add + 1))
else:print("查找失败")

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

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