1.适用条件

原问题可以归约为独立求解的子问题。子问题要与原问题有相同的类型，即每一个子问题与原问题除了数据的规模不相同外，解决问题的方法完全相同。
特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题;
分解出的子问题的解可以合并为原问题的解；
分解出的各个子问题是相互独立的。

2.典型问题

1.二分检索

https://blog.csdn.net/qq_44766883/article/details/107039935
输入：数组a[]，数组长度len，查找的数值target
输出：查找到元素的下标，若未找到则返回-1

//二分搜索
int binarySearch(int arr[],int len,int target){
      int left=0;
      int right=len-1;
      int mid;
      while(left<=right){
            mid=(left+right)/2;
            if(target<arr[mid]){
                  right=mid-1;
            }else if(target>arr[mid]){
                  left=mid+1;
            }else if(target==arr[mid]){
                  return mid;
            }
      }
      return -1;
}

2.归并排序

https://blog.csdn.net/doubleguy/article/details/81390951

归并排序
输入：数组a[]，最左端下标left和最右端下标right

void merge(int a[],int temp[],int left,int mid,int right)//排序、合并
//a[]为待排序数组，temp[]为临时数组，left为左边数组的最小下标，right为右边数组的最大下标，mid为左边数组的最大下标，mid+1为右边数组的最小下标
{
  int i=left,j=mid+1;//分别记录两个数组第一个数的下标，用作比较
  int m=mid,n=right;//分别记录两个数组最后一位的下标，用作限定范围
  int k=0;//初始化临时数组指针
  while(i<=m&&j<=n)//限定范围
  {
    //开始作比较
    if(a[i]<=a[j])                   //如果左边小于右边
      temp[k++]=a[i++];              //把左边的数插入临时数组
    else                             //如果右边小于左边
      temp[k++]=a[j++];              //把右边的数插入临时数组
  }
   while(i<=m)                       //若左边数组还有剩余，把剩下的全都插入temp[]
      temp[k++]=a[i++]; 
   while(j<=n)                       //若右边数组还有剩余，把剩下的全都插入temp[]
      temp[k++]=a[j++];
   for(i=0;i<k;i++)                  //将临时数组里以及排好序的数据复制到原数组
      a[left+i]=temp[i];
}
void mergesort(int a[],int left,int right)//递归实现归并排序，这个函数主要是“分”的作用
{
  if(left<right)//设置递归回归点，即左指针大于（等于）右指针的时候停止向下递归
  {
    int mid=(left+right)/2;//从中间分开
    int b[1000];//临时数组
    mergesort(a,left,mid);//向左递归
    mergesort(a,mid+1,right);//向右递归
    merge(a,b,left,mid,right);//对这一层进行归并，b为临时数组

  }
}

3.快排

https://blog.csdn.net/li528405176/article/details/86645708
快排的关键在于如何划分数组，方法多种多样，上面博客讲了三种不同的划分数组的方法，我这边只写一种，即追赶指针法
输入：待排序数组a[]，起始位置left，终止位置right.

void quicksort(int a[],int left,int right)
{
  if(left<right)//递归的回归点
  {
    int h=left,q=left+1,x=a[left];//h,q分别为后指针和前指针，x是快排的基准元素
    for(q;q<right;q++)//前指针扫描整个数组
    {
       if(a[q]<x)//如果遇到小于基准的数
       {
        h++;//则后指针加一
        if(q!=h)swap(a[q],a[h]);//如果前后指针指向的不是一个数，那必然是前指针指向小于基准的，后指针指向大于基准的数，交换                                                                                                                                         
       }
    }
    //扫描结束后，后指针此时必定指向一个小于基准的数（因为已经和前指针交换完毕），这时只需将基准和后指针的数交换即可
    swap(a[left],a[h]);
    quicksort(a,left,h-1);//递归
    quicksort(a,h+1,right);
  }
}

4.选择算法

5.幂乘

5.多项式求值