Algorithm 中文意思是算法，是一个计算的具体步骤，常用于数据处理、计算以及自动推理。它作为 C++ 标准模版库 STL 中最重要的头文件之一，其提供了大量非成员模版函数，例如排序操作、二分查找操作、集合操作以及堆操作等。同时可以通过迭代器或指针访问任何对象序列，例如 STL 容器数组或实例。更多的了解请参考官方文档 。
本实训主要设置了四个关卡：第一关和第二关介绍了 Algorithm 中的二分搜索操作 binary_search 及其相关搜索操作；第三关是修改序列操作 Modifying sequence operations ；第四关讲的是非修改序列操作 Non-modifying sequence operations 。最后在每个关卡都设置了实例，考察学员对所讲内容的理解和在线编程能力。
第1关：二分查找：在N个无序整数里面查找M个指定整数
任务描述
本关任务：给定包含 N 个整数的无序序列 S(a1,a2,..,aN)，以及 M 次查询序列 Q(b1,b2,..,bM)，判定 bj 是否在序列 S 中。
相关知识
为了完成本关任务，你需要掌握：1.解题思路，2.快速排序算法，3.二分查找算法。
解题思路
本关卡问题清晰，解法简单：对于每次查询bj，在序列S中遍历ai是否等于bj。虽然该解法实现简单，但是执行效率低，运算复杂度高O(N×M)。
高效解法：首先运用快速排序算法，将无序序列变为有序（升序），然后对每次查找操作，使用二分查找算法判断元素是否存在。该解法实现稍微有点复杂，但是执行效率高，运算复杂度低O(N×logN+M×logN)。
快速排序算法
快速排序算法的背景和原理前面已有很多实训介绍过了，为了方便实现，一般使用 algorithm 中模板函数 sort ，请认真参考实训《算法与竞赛(第2章) - C++与Algorithm基础一》 的第三个关卡，之后的实训将不再对sort进行讲解。
二分查找算法
二分查找算法也称折半查找算法 Binary Search Algorithm ，它是一种效率较高的查找方法，复杂度为O(logN)。二分查找算法要求线性表（序列）必须采用顺序存储结构，而且表中元素按关键字有序排列。
核心思想：将表中间位置记录的关键字与待查找的关键字进行比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
幸运的是，C++ 在 Algorithm 算法模板中集成了二分查找算法，这样仅仅调用一个模板函数 binary_search 就可以实现指定元素（关键字）的查找了。其函数原型及其应用实例如下：
1 \\ binary_search函数原型
2 default (1):
3 template <class ForwardIterator, class T>
4 bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7 bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
8 \\ binary_search应用实例
9 int arr[4] = {1,2,3,4}; // 升序数组
10 bool judge1 = binary_search(arr, arr+4, 1); // judge1结果为true
11 bool judge2 = binary_search(arr, arr+4, 5); // judge2结果为false
本关卡使用的是整型数据，使用默认的模板函数即可。若有兴趣学习自定义数据类型下的二分查找，请参考实训《算法与竞赛(第2章) - C++与Algorithm基础一》第三个关卡对自定义数据类型的相关操作。
编程要求
本关的编程任务是补全右侧代码片段 main 中 Begin 至 End 中间的代码，具体要求如下：
在 main 中，读取N个无序序列，并存储在数组中，然后对无序数组进行排序，最后调用二分查找算法完成 M 次指定元素的查找任务，并输出查找结果。若在序列中，输出 bj in array，否则输出 bj not in array。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
7
2 5 9 5 5 3 1
3
4 7 5
预期输出：
4 not in array
7 not in array
5 in array
输入格式：
第一行：序列元素个数N
第二行：N个无序序列元素
第三行：查询次数M
第四行：M个待查询元素
输出格式：
输出M行，每行对应查询结果，每行末尾换行！！！
开始你的任务吧，祝你成功！
1 //
2 // main.cpp
3 // step1
4 //
5 // Created by ljpc on 2018/7/8.
6 // Copyright ? 2018年 ljpc. All rights reserved.
7 //
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstdio>
12
13 using namespace std;
14
15 int main(int argc, const char * argv[])
16 {
17
18 // 请在这里补充代码，完成本关任务
19 /********** Begin *********/
20 int n,m;
21 cin>>n;
22 int a[n+10];//需要注意的是，有的编译器支持这种定义方法，有的不支持
23 //可以考虑直接定义一个很大的数组
24 //如果这样定义的话，顺序不能颠倒，只有有了n之后才可以定义这个数组
25
26 for(int i=1;i<=n;i++) cin>>a[i];//依次输入这n个无序序列并储存在数组中
27
28 sort(a,a+n+1);//利用sort函数对无序数组进行排序，sort默认使用 < 号
29
30 cin>>m;
31 int b[m+10];
32 for(int i=1;i<=m;i++)
33 cin>>b[i];
34
35 for(int i=1;i<=m;i++){//利用for循环依次对数组中存储的每一个数在有序数组a中进行查找
36 if(binary_search(a,a+n,b[i])) //binary_search函数题目中有写到，是对有序数组进行查找的
37 cout<<b[i]<<" in array"<<endl;
38 else cout<<b[i]<<" not in array"<<endl;
39 }
40 /********** End **********/
41
42 return 0;
43 }
点击查看代码
第2关二分查找：在N个有序整数里面查找M个指定整数的闭区间位置
任务描述
本关任务：给定包含N个整数的升序序列S(a1,a2,..,aN)，以及M次查询序列Q(b1,b2,..,bM)，求bj在序列S中的闭区间位置（测试数据保证bj存在序列S中），例如2在升序序列 1，2，2，3 中的闭区间位置为 [1,2] 。
相关知识
为了完成本关任务，你需要掌握：1.模板函数 lower_bound ，2.模板函数 upper_bound ，3.模板函数 equal_range 。
模板函数 lower_bound
上个关卡介绍了 binary_search 的模板函数，实际上它的内部实现是基于 lower_bound 函数实现的，通过 lower_bound 在有序序列里查找不小于关键字的元素，并返回元素索引位置最低的地址，最后根据地址来判断是否查找成功，代码如下：
1 template <class ForwardIterator, class T>
2 bool binary_search (ForwardIterator first, ForwardIterator last, const T& val){
3 first = std::lower_bound(first,last,val);
4 return (first!=last && !(val<*first));
5 //first!=last为true：说明找到一个不小于关键字的元素
6 //!(val<*first) 为true：说明该元素与待查找关键字相等
7 }
模板函数 lower_bound 的基本用途是查找有序区间中第一个 大于或等于 某给定值的元素的位置，由此本关卡的任务可以利用 lower_bound 获取序列中等于待查找关键字的元素的位置。其函数原型及其应用实例如下：
1 \\ 函数原型
2 default (1):
3 template <class ForwardIterator, class T>
4 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);
8 \\ 应用实例
9 int arr[5] = {1,2,2,4,5};
10 int a = lower_bound(arr, arr+5, 2) - arr; // a结果为1
模板函数 upper_bound
模板函数 upper_bound 的基本用途与 lower_bound 相对，是查找有序区间中第一个 大于 某给定值的元素的位置，由此本关卡的任务可以利用 upper_bound 获取序列中第一个 大于 待查找关键字的元素的位置，往前移一位就是最后一个等于待查找关键字的元素的位置。其函数原型及其应用实例如下：
1 \\ 函数原型
2 default (1):
3 template <class ForwardIterator, class T>
4 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
5 custom (2):
6 template <class ForwardIterator, class T, class Compare>
7 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
8 \\ 应用实例
9 int arr[5] = {1,2,2,4,5};
10 int b = upper_bound(arr, arr+5, 2) - arr; // b结果为3
模板函数 equal_range
模板函数 equal_range 综合了 lower_bound 和 upper_bound 的功能，通过内部调用这两个上下界查找函数，返回两个地址并组成 pair ：第一个地址是序列中第一个大于等于待查找关键字的元素位置，而第二个地址是第一个大于待查找关键字的元素位置。因为本关卡的数据保证在序列中存在待查找关键字，所以 equal_range 返回的是一个左闭右开的区间位置。其函数原型及其应用实例如下：
1 default (1): 2 template <class ForwardIterator, class T> 3 pair<ForwardIterator,ForwardIterator> 4 equal_range (ForwardIterator first, ForwardIterator last, const T& val); 5 custom (2): 6 template <class ForwardIterator, class T, class Compare> 7 pair<ForwardIterator,ForwardIterator> 8 equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
模板函数 equal_range 基于 lower_bound 和 upper_bound 的函数内部实现如下：
1 \\ 函数原型
2 template <class ForwardIterator, class T>
3 pair<ForwardIterator,ForwardIterator>
4 equal_range (ForwardIterator first, ForwardIterator last, const T& val){
5 ForwardIterator it = std::lower_bound (first,last,val);
6 return std::make_pair ( it, std::upper_bound(it,last,val) );
7 }
8 \\ 应用实例
9 int arr[5] = {1,2,2,4,5};
10 auto bounds = equal_range(arr, arr+5, 2);
11 int a = bounds.first-arr; // a结果为1
12 int b = bounds.second-arr; // b结果为3
编程要求
本关的编程任务是补全右侧代码片段 main 中 Begin 至 End 中间的代码，具体要求如下：
在 main 中，读取 N 个升序序列，并存储在数组中，基于 lower_bound 和 upper_bound 算法（或 equal_range ）完成M次指定元素的查找任务，并输出查找闭区间结果（输出格式严格遵循样例）。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
测试输入：
7
1 1 2 3 5 5 6
2
5 6
预期输出：
5 at order array position [4,5]
6 at order array position [6,6]
输入格式：
第一行：序列元素个数N
第二行：N个升序序列元素
第三行：查询次数M
第四行：M个待查询元素
输出格式：
输出M行，每行对应查询结果，每行末尾换行！！！
开始你的任务吧，祝你成功！