主要讲了三个基础算法的思想和模板，以及一些例题

基础算法思想和模板

快速排序

思想：对于所要排序的区间，设置两个指针为 i(初始值为 l-1 ) 和 j(初始值为 r+1 )，以及一个枢纽值(一般取中间位置的值)，将 i 和 j 移动到可以进行交换的地方(i 位置的值大于枢纽值时可交换，j 位置的值小于枢纽值时可交换)，进行交换，直至 i 与 j 相遇( 满足i>=j )。
然后对由i（或者 j ）分割开的左右两个区间分别进行快速排序。

#include <iostream>
#include <algorithm>

const int N = 1000010;
int n;
int q[n];

using namespace std;

void quick_sort(int q[], int l, int r)
{
    if(l>=r) return;
    int i=l-1, j=r+1, x=q[l+r>>1];
    while(i<j)
    {
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<=j) swap(q[i], q[j]);
    }
    quick_sort(q, l, i);
    quick_sort(q, i+1, r);
}
int main(void)
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d", &q[i]);

    quick_sort(q, 0, n-1);

    for(int i=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个边界问题
1. 循环的大条件是while(i<j)，而不是while(i<=j)
2. 判断左移和右移是<和>而不是<=和>=
以上两个地方从思路上来考虑没有问题，但是在实际数据中运行可能会导致无限循环，所以要记得这两个地方。

归并排序

思想：对于所要排序的区间，设置两个指针 i(初始值为区间左边界 l)和 j(初始值为区间中间位置 l+r>>1)，两者后移时将所指向的较小值放入 tmp[] 数组，直至 i==mid 或者 j==r，然后把左半边或者右半边剩余的全部移进 tmp[] 数组，实现排序，最后把 tmp[] 数组中的元素拷贝到原数组的[l, r]区间。
注意，递归的位置在排序之前。

#include <iostream>

const int N=1e6+10;
int n;
int q[N],tmp[N];

using namespace std;

void merge_sort(int q[], int l, int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    int i=l, j=mid+1, k=0;
    merge_sprt(q, l, mid);
    merge_sort(q, mid+1, r);
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];

    for(i=l, j=0; i<=r; i++,j++) q[i]=tmp[j];
}
int main(void)
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d", &q[i]);

    merge_sort(q, 0, n-1);

    for(int i=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个问题
1. 递归在排序之前
2. i=l, j=mid+1
3. tmp[] 数组从0开始存放和拷贝

二分查找

思想：对于一个区间，如果某种性质能够将区间分为前后两个部分(check()为True和False)，那么可以用递归的方式找到满足与不满足的分界点，递归的方式是逐步地缩小查找的区间，并且每次只check此区间中间位置的值是否满足，注意这里“递归”的实现是循环。

bool check(int x) // 检查是否满足某种性质
{
    /* ... */
}

int bsearch_1(int l, int r)
{
    while(l<r)
    {
        int mid= l+r >> 1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

int bsearch_2(int l, int r)
{
    while(l<r)
    {
        int mid= l+r+1 >>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

bool check(double x)// 检查是否满足某种性质
{
    /* ... */
}

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;
    while(r-l>eps)
    {
        double mid = (l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    return l;
}

需要注意的问题
1. 如果所写的check()函数为 True 时，需要将 l 更新为 mid，那么 mid 应该用 l+r+1 >> 1（原因可能是正整数移位取整是向下取整，不+1 可能会导致 l=l，从而导致无无限循环）