企业官网建设流程全解析

前言

在一个数组里同时找最大值和最小值，看起来是最基础不过的练习，但很多实现都停留在「跑两遍循环」或者「一次循环里对每个元素同时比两次」的层次。典型误解有两个：一是认为必须遍历两遍才能分别拿到最大值和最小值；二是认为只要写成一个for循环，比较次数就已经最优了。实际上，把元素两两配对（pairwise comparison）可以把比较次数从2n-2降到大约3n/2，这是算法教科书里讨论比较次数下界的经典例子。

本文讲三件事：配对法的原理和比较次数推导、奇数长度与空数组的边界处理、以及它与标准库std::minmax_element的关系。代码以 C++17 为基准，只按标准语义推演，不依赖任何特定编译器。

需要先说明一点：比较次数的最优并不等于实际耗时最优。现代处理器上，一次额外的比较往往被流水线和分支预测掩盖，真正影响性能的可能是缓存访问模式和函数是否被内联。所以本文讨论的是比较次数这个可精确计数的指标，而不是承诺某种速度提升。

一、朴素做法与比较次数的下界

最直观的写法是初始化min和max为第一个元素，然后从第二个元素开始，每个元素分别与当前最小值、当前最大值比较一次：

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

int main() {
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
if (v.empty()) return 0;

int lo = v[0], hi = v[0];
for (std::size_t i = 1; i < v.size(); ++i) {
if (v[i] < lo) lo = v[i];
if (v[i] > hi) hi = v[i];
}
std::cout << lo << ' ' << hi << '\n';
return 0;
}

这段代码对n个元素做2(n-1)次比较，也就是2n-2次。它的优点是简单、分支少、对缓存友好；缺点是比较次数不是最少的。

为什么说2n-2不是下界？可以用「候选集合」来论证。一开始，每个元素都既可能是最大值，也可能是最小值。一次比较a < b能做的事情是：把a从「最大值候选」里排除，把b从「最小值候选」里排除。也就是说，一次比较最多让两个候选出局。要让最大值候选只剩一个、最小值候选只剩一个，总共需要排除2n-2个候选身份，而下界因此是n-1次比较——但这是把两种身份混在一起算的粗糙下界。更精细的对手论证会区分「两个都还是候选的元素之间的比较」和「候选与当前极值之间的比较」：前者一次能排除两个身份，后者一次只能排除一个。最终可以证明下界是⌈3n/2⌉ - 2，配对法正好达到这个界。

二、配对法的步骤

配对法的思路是把元素分成若干对，先在每对内部比较一次，确定这一对的较大者和较小者，再让较大者去挑战当前最大值、较小者去挑战当前最小值。这样每对元素固定花 3 次比较，而不是 4 次。

具体步骤：

1. 
   
2. 若数组长度小于 2，直接返回（空数组无解，单元素的最大最小值都是它自己）。
3. 
   
4. 取前两个元素比较一次，较大者作为hi，较小者作为lo。
5. 
   
6. 从第三个元素开始，每次取两个元素a、b，先比较a与b（1 次），把较小者与lo比较、较大者与hi比较（2 次）。
7. 
   
8. 如果元素个数是奇数，最后会剩下一个元素，让它分别与lo、hi比较（2 次）。
9. 
   

比较次数的计算：

• 
  
• n为偶数时：第 2 步 1 次，剩下n-2个元素组成(n-2)/2对，每对 3 次，总计1 + 3(n-2)/2 = 3n/2 - 2。
• 
  
• n为奇数时：第 2 步 1 次，中间(n-3)/2对共3(n-3)/2次，最后一个元素 2 次，总计(3n-3)/2，与⌈3n/2⌉ - 2一致。
• 
  

对照2n-2，当n较大时两者相差约n/2次比较。这就是配对法唯一但实在的收益。

三、C++17 完整实现

下面的实现把结果包在std::optional里，用来表达「空数组没有结果」这一情况。模板参数T需要可拷贝构造、可用<比较。这里没有用std::numeric_limits<T>::max()做初始值，因为对自定义类型或浮点类型那样写并不总是合适，直接用首元素更稳妥。

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

template <typename T>
std::optional<std::pair<T, T>> min_max_pairwise(const std::vector<T>& v) {
const std::size_t n = v.size();
if (n == 0) return std::nullopt;
if (n == 1) return std::make_pair(v[0], v[0]);

T lo, hi;
if (v[0] < v[1]) {
lo = v[0];
hi = v[1];
} else {
lo = v[1];
hi = v[0];
}

std::size_t i = 2;
for (; i + 1 < n; i += 2) {
T a = v[i];
T b = v[i + 1];
if (b < a) std::swap(a, b); // 保证 a <= b
if (a < lo) lo = a;
if (hi < b) hi = b;
}

if (i < n) { // 奇数个元素，剩下最后一个
if (v[i] < lo) lo = v[i];
if (hi < v[i]) hi = v[i];
}

return std::make_pair(lo, hi);
}

int main() {
std::vector<int> even{3, 1, 4, 1, 5, 9, 2, 6};
std::vector<int> odd{7, -2, 8, 0, 5};
std::vector<int> empty;

if (auto r = min_max_pairwise(even)) {
std::cout << "even: " << r->first << ' ' << r->second << '\n';
}
if (auto r = min_max_pairwise(odd)) {
std::cout << "odd: " << r->first << ' ' << r->second << '\n';
}
if (!min_max_pairwise(empty)) {
std::cout << "empty: no result\n";
}
return 0;
}

逐处核对几个细节：

• 
  
• 循环条件是i + 1 < n，保证进入循环时v[i]和v[i+1]都存在；i是无符号的std::size_t，用i + 1 < n而不是i < n - 1可以避免n == 0时n - 1回绕。虽然前面已经处理了n == 0，但保持这个写法更稳。
• 
  
• T a = v[i];是拷贝。如果T是大型对象，可以改成const T&再配合std::minmax，但那会引入额外的引用和生命周期考虑，本文选择直观的拷贝。
• 
  
• 返回类型是值，不涉及悬垂引用。std::optional在无值时不会构造pair，所以不需要T可默认构造，只需要可拷贝构造。
• 
  
• 严格来说std::pair<T,T>要求T可拷贝构造，这里满足。
• 
  

四、与 std::minmax_element 的对照

标准库在<algorithm>里提供了std::minmax_element，签名是：

// 适用于 C++17
template<class ForwardIt, class Compare>
std::pair<ForwardIt, ForwardIt>
minmax_element(ForwardIt first, ForwardIt last, Compare comp);

template<class ForwardIt>
std::pair<ForwardIt, ForwardIt>
minmax_element(ForwardIt first, ForwardIt last);

返回的pair中，first指向最小元素，second指向最大元素；如果区间为空，返回{last, last}（即{first, first}）。标准规定的比较次数上限是max(⌊3/2·(N-1)⌋, 0)次，也就是说标准库实现通常已经采用了与本文相同的配对策略。

两者的差别主要在接口层面：

如果只是需要对一个容器求极值，直接调用std::minmax_element更省事，也更不容易在边界上写错。手写配对法的价值主要在于教学、嵌入式环境（不想引入算法头文件的迭代器抽象），或者需要在遍历过程中顺带做别的事情。

常见坑点

1. 用类型极值初始化，遇到更宽的类型就出错

❌int lo = INT_MAX;然后拿去和long long元素比较，若所有元素都大于INT_MAX，结果错误。

✅ 用首元素初始化，或者用std::numeric_limits<T>::max()且保证T就是元素类型。

2. 空容器直接解引用

❌int lo = *v.begin();对空vector是未定义行为（undefined behavior, UB）。

✅ 先判断v.empty()，返回std::optional或抛出异常。

3. 把「写成一个循环」当成「比较次数最优」

❌ 循环体里对每个元素先比lo再比hi，并声称已经优化。

✅ 明确比较次数：那种写法仍是2n-2；要减少比较次数必须两两配对。

4. 给算法传<=作为比较器

❌std::minmax_element(v.begin(), v.end(), [](int a, int b){ return a <= b; });

✅ 比较器必须满足严格弱序（strict weak ordering），用<；<=不满足反对称性，行为未定义。

5. 返回指向局部数据的指针或引用

❌ 函数内int tmp[2]然后返回std::pair<int*, int*>。

✅ 返回值类型，或由调用方提供存储；本文返回std::pair<T,T>。

6. 多线程各自更新同一组全局极值

❌ 多个线程无同步地写同一个g_min、g_max，这是数据竞争（data race），属于 UB。

✅ 每个线程算局部结果，最后在主线程合并；或者用互斥量保护。

7. 对浮点数组忽略 NaN

❌ 默认<比较能正确处理NaN；实际上NaN < x和x < NaN都为false，结果依赖元素顺序。

✅ 先明确业务上是否允许 NaN；需要时先过滤，或使用能识别 NaN 的比较逻辑。

总结

同时取最大最小值的核心不是「少写一个循环」，而是让每次比较尽量淘汰两个候选身份。理解了这一点，3n/2这个数字就是自然推出来的，而不是背下来的。工程中优先用std::minmax_element，需要自己实现时务必把空区间、单元素、奇数长度这三种边界写全。