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行，每行对应查询结果，每行末尾换行！！！

开始你的任务吧，祝你成功！