c++和python实现顺序查找实例

前言

顺序查找（sequential search，也叫线性查找 linear search）是最基础的查找算法：从一端开始，逐个比较，直到找到目标或者走完整个序列。它不要求数据有序，也不需要额外的数据结构，是很多查找场景的兜底方案。

常见的误解是「有了二分查找，顺序查找就没用了」。二分查找虽然快，但要求数据有序且支持随机访问；链表、无序数组、数据量很小、或者只查一次的场景，顺序查找反而更合适——排序的 O(n log n) 成本可能远高于一次 O(n) 扫描。

另一个误解是「顺序查找太简单，没什么可讲的」。实际写起来，C++ 里返回下标还是迭代器、找不到时返回什么、无符号类型怎么处理，Python 里用in还是index()、找不到时抛异常还是返回 -1，都有取舍。这些细节决定了函数好不好用。

本文用 C++ 和 Python 各实现一版，对比两种语言在类型、返回值、异常处理上的差异，最后给出适用场景和常见坑点。

一、算法与复杂度

伪代码：

for i from 0 to n - 1:
if a[i] == target:
return i
return NOT_FOUND

• 
  
• 最好情况：目标在第一个位置，1 次比较。
• 
  
• 最坏情况：目标在最后或不存在，n 次比较。
• 
  
• 平均情况：约 n/2 次比较（假设目标等概率出现在各位置）。
• 
  
• 时间复杂度 O(n)，空间复杂度 O(1)。
• 
  

顺序查找的唯一前提是「元素可比较相等」。它不要求有序，不要求随机访问（链表也能用），这是它相对二分查找的优势。

1.1 哨兵优化

有一种减少循环内边界判断的技巧叫哨兵（sentinel）：在数组末尾放一个等于目标的值，这样循环一定会在数组内终止，省去i < n的判断。

// 适用于 C++17
// 前提：数组末尾有额外空间，且查找后能恢复原值
int sentinel_search(int* a, int n, int target) {
int last = a[n - 1];
a[n - 1] = target; // 放置哨兵
int i = 0;
while (a[i] != target) ++i; // 不需要判断 i < n
a[n - 1] = last; // 恢复
if (i < n - 1 || a[n - 1] == target) return i;
return -1;
}

这个优化在现代处理器上未必更快：分支预测对规整的循环判断通常很准，而哨兵写法多了一次写内存、一次恢复，还可能破坏只读数据。除非在特定嵌入式环境且有测量依据，否则不建议为了「省一次比较」引入这种复杂度。

二、C++ 实现

2.1 返回下标

// 适用于 C++17
#include <cstddef>
#include <vector>

// 找不到返回 -1；用 std::ptrdiff_t 而不是 size_t，才能表示「无效」
std::ptrdiff_t linear_search(const std::vector<int>& data, int target) {
for (std::size_t i = 0; i < data.size(); ++i) {
if (data[i] == target) {
return static_cast<std::ptrdiff_t>(i);
}
}
return -1;
}

这里刻意用std::ptrdiff_t（有符号）作为返回类型。如果用std::size_t返回 -1，会回绕成一个巨大的正数，调用方写if (pos >= 0)永远为真，这是 C++ 里最典型的查找 bug 之一。

2.2 返回迭代器

更通用的写法接受一对迭代器，返回指向目标元素的迭代器，找不到返回last：

// 适用于 C++17
template <typename InputIt, typename T>
InputIt linear_find(InputIt first, InputIt last, const T& value) {
for (; first != last; ++first) {
if (*first == value) {
return first;
}
}
return last;
}

这种风格与标准库一致：std::find的签名就是find(first, last, value)，返回迭代器，找不到返回last。用last而不是end() - 1之类，是因为InputIt可能不支持随机访问（比如输入流迭代器），不能做减法。

调用方判断：

// 适用于 C++17
auto it = linear_find(v.begin(), v.end(), 42);
if (it != v.end()) {
std::cout << "found: " << *it << '\n';
}

标准库已经提供了std::find，功能完全相同。自己实现的价值主要是教学，或者需要额外的副作用（比如统计比较次数）。生产代码优先用std::find，它经过优化，语义也更统一。

2.3 泛型与自定义比较

如果需要按字段查找，可以传一个谓词：

// 适用于 C++17
template <typename InputIt, typename Pred>
InputIt find_if_custom(InputIt first, InputIt last, Pred pred) {
for (; first != last; ++first) {
if (pred(*first)) return first;
}
return last;
}

标准库对应的是std::find_if。

三、Python 实现

3.1 基本版本

# 适用于 Python 3
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
return -1

enumerate同时给出下标和值，比range(len(items))再取items[i]更清晰，也少一次下标访问。

Python 是动态类型，返回-1表示未找到是常见约定，但也有另一种风格：找不到返回None。两者的区别在于，None不会被误当成合法下标，而-1在 Python 里是合法的负索引（items[-1]表示最后一个元素）。如果调用方直接把返回值拿去索引，-1会静默取到最后一个元素，这是真实存在的 bug 来源。

# 适用于 Python 3
pos = linear_search(data, target)
if pos != -1:
print(data[pos])

必须显式判断，不能写if pos:——下标 0 会被当成假值。

3.2 使用内置设施

Python 的in运算符和list.index()都内置了线性查找：

# 适用于 Python 3
if target in items: # 只判断存在性，O(n)
print("found")

pos = items.index(target) # 找不到抛 ValueError

index()找不到时抛出ValueError，不是返回 -1。这一点和 C++ 的约定不同，跨语言移植代码时容易忽略。需要容错时用try/except，或者先in再index（最坏情况扫两遍）。

对需要自定义比较规则的场景，可以用生成器表达式配合next：

# 适用于 Python 3
pos = next((i for i, v in enumerate(items) if v.age > 30), -1)

next的第二个参数是默认值，找不到时返回 -1，避免StopIteration。

四、两种实现的对比

维度	C++	Python

返回下标类型

std::ptrdiff_t（有符号）

int（任意精度）

未找到的表示

返回 -1 或last迭代器

返回 -1 /None，或抛ValueError

泛型方式

模板 + 迭代器

鸭子类型，任意可迭代对象

边界检查

无，越界是 UB

有，越界抛IndexError

典型调用

std::find

in/list.index()

适用容器

数组、vector、list、流迭代器

list、tuple、生成器、任何可迭代对象

C++ 版本的优势是零开销的泛型：模板对每种类型生成专门代码，迭代器抽象在编译期展开。代价是要自己处理类型和边界。Python 版本短小、安全，但每次比较都有解释器开销，且动态类型让「返回 -1 还是 None」这种约定只能靠文档。

完整示例

C++：

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <vector>

std::ptrdiff_t linear_search(const std::vector<int>& data, int target) {
for (std::size_t i = 0; i < data.size(); ++i) {
if (data[i] == target) {
return static_cast<std::ptrdiff_t>(i);
}
}
return -1;
}

int main() {
const std::vector<int> data{4, 8, 15, 16, 23, 42};
const int targets[] = {15, 100, 4};

for (int t : targets) {
const std::ptrdiff_t pos = linear_search(data, t);
if (pos != -1) {
std::cout << t << " at " << pos << '\n';
} else {
std::cout << t << " not found\n";
}
}
return 0;
}

按标准语义，输出依次是15 at 2、100 not found、4 at 0。

Python：

# 适用于 Python 3
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index
return -1


if __name__ == "__main__":
data = [4, 8, 15, 16, 23, 42]
for target in (15, 100, 4):
pos = linear_search(data, target)
if pos != -1:
print(f"{target} at {pos}")
else:
print(f"{target} not found")

两段程序的输出语义一致。注意 Python 版本用pos != -1而不是if pos，避免下标 0 被误判。

常见坑点

1. 
   
2. ❌ C++ 用size_t返回 -1：
3. 
   

``cpp std::size_t pos = ...; return -1; // 变成 SIZE_MAX`✅ 用有符号类型std::ptrdiff_t，或返回迭代器 /std::optional<std::size_t>`。

1. 
   
2. ❌ 用if (pos)判断 Python 下标：
3. 
   

``python if pos: print(data[pos]) # 下标 0 时被跳过`✅if pos != -1:`。

1. 
   
2. ❌ 循环条件写成i <= n：
3. 
   

``cpp for (std::size_t i = 0; i <= data.size(); ++i) // 越界`✅i < data.size()`。

1. 
   
2. ❌ 找到后忘记return，继续循环：
3. 
   

``cpp if (data[i] == target) { /* 什么也没做 */ }`` ✅ 找到立即返回下标或迭代器。

1. 
   
2. ❌ 函数末尾漏掉「未找到」的返回，导致 UB：
3. 
   

``cpp int search(...) { for (...) { ... } } // 没有 return`✅ 循环后显式return -1;或return last;`。

1. 
   
2. ❌ 对浮点数直接用==比较。
3. 
   

✅ 用 epsilon 范围比较，或改用整数/定点表示。

1. 
   
2. ❌ Python 直接调用list.index()却不处理ValueError。
3. 
   

✅ 用try/except，或先in判断。

1. 
   
2. ❌ 对已排序的大数组仍用顺序查找。
3. 
   

✅ 有序且随机访问时用二分查找（std::lower_bound/bisect）。

总结

要点	C++	Python

核心循环

迭代器或下标遍历

for ... in enumerate(...)

未找到

-1 /last

-1 /None/ 异常

类型安全

编译期检查

运行期检查

推荐设施

std::find、std::find_if

in、list.index

顺序查找的算法本身没有难度，工程上的差异全在「找不到时返回什么」和「类型是否能有符号地表示无效值」。C++ 里避开无符号返回类型，Python 里避开if pos的真值判断，这两个坑绕过去，代码就稳了。