分治思想的定义

分治思想是C++中很重要的一个思想，它的主旨是“将大的问题化作小的问题，将小问题在化作更小的问题”。就是这样一个看起来十分简单的思想，却涵盖了许许多多的算法，如递归，递推，贪心等。

分治思想的其中一个方式就是我们耳熟能详的“二分法”，这个所谓的“二分法”主要用于搜索问题，当我们遇到一个可能无限长且有序（注意，一定要有序）的一维数组时，用寻常的遍历法显然不可能了，因为这样很容易超时，这时，我们就可以用到二分法了。二分法就是将一个一维数组平均分成两段，选取一个中间值，然后通过某条件判断选择其中一段，再重复以上操作，直到找到我们要找的数为止。

以“1、2、3、4、5、6、7、8、9、10”为例，我们要查找的数为7，先将数组分为“1、2、3、4、5”和“6、7、8、9、10”，选取5为中间值，发现7>5，所以选第二段，再将数组分为“6、7、8”和“9、10”选取8为中间值，发现7<8，所以选第一段，再将数组分为“6、7”和“8”，选取7为中间值，发现7=7，就找到了。

二分法相对普通遍历来说大大减少了循环次数，也就减少了时间复杂度，就更不容易超时。

二分法

输入：先输入一个数n，代表数组有几个数，再输入一行数，代表n个数字（中间用空格隔开），最后输入一个数m，代表要查找的数是几。

输出：输出为一个数，代表所要查找的数在数组中排行第几（因代码写法原因，输出值与实际值相差1），如未找到则输出-1。

输入复制

10

1 2 3 4 5 6 7 8 9 10

7

输出复制

6

#include<bits/stdc++.h>
using namespace std;
int func(int,int);
int a[1010]={0};
int n,m;
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i];}cin>>m;cout<<func(0,n-1);return 0;
}
int func(int s,int e)
{if(e-s<=1){if(a[s]==m){return s;}else if(a[e]==m){return e;}else{return -1;}}int mid=(s+e)/2;if(a[mid]==m){return mid;}else if(a[mid]>m){return func(s,mid);}else if(a[mid]<m){return func(mid+1,e);}
}

归并排序

题目描述：输入两个值（n，m），再分别输入两行数据（a[n],b[m]），将他们归并为一个数列，要求这个数列必须从小到大排列。输入：输入分四行，第一行为一个值n，代表第一行数据有几个。第二行为n个数据，代表第一组数据a。第三行为一个值m，代表第四行数据有几个。第四行为m个数据，代表第二组数据b。输入：输出为一行数据，代表数据a与数据b归并后的数据。

输入复制

5

1 3 5 5 8

3

2 6 9

输出复制

1 2 3 5 5 6 8 9

#include<bits/stdc++.h>
using namespace std;
int a[110]={0};
int b[110]={0};
int c[250]={0};
int n,m;
int lc=0;
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>a[i];}cin>>m;for(int i=0;i<m;i++){cin>>b[i];}int i=0,j=0;while(i<n&&j<m){if(a[i]<=b[j])c[lc++]=a[i++];else c[lc++]=b[j++];}while(i<n)c[lc++]=a[i++];while(j<m)c[lc++]=b[j++];for(int k=0;k<lc;k++){cout<<c[k]<<" ";}return 0;
}