排序和二分的笔记

1 排序

1.1 快速排序

基于分治，不稳定的排序

确定分界点：q[l]，q[(l+r)/2]，q[r]，随机（即左边界，中间数，有边界，随机）
调整区间：小于分界点的数在左边，大于分界点的数在右边
递归处理左右两端

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r) {
    if (l >= r) return; // 终止条件
    int x = q[(l + r) >> 1], i = l - 1, j = 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, j);
    quick_sort(q, j + 1, r);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
    return 0;
}

说明：

如果x选取q[l]，则递归时参数范围选择(l, j)和(j + 1, r)

如果x选取q[r]，则递归时参数范围选择(l, i - 1)和(i, r)

如果x选取q[l + r >> 1]，则递归时参数范围选择哪种都行

证明：

反例：

如果算法x选取q[l]，即x = q[0] = 1，递归时参数范围选择(l, i - 1)和(i, r)，则下一次迭代后i = 0，j = 0，递归时参数的范围为(0, -1)和(0, 1)，其中第1个递归无效，第2个递归与之前一致，陷入死循环。

同理如果算法x选取q[r]，即x = q[1] = 2，递归时参数范围选择(l, j)和(j + 1, r)，则下一次迭代后i = 1，j = 1，递归时参数的范围为(0, 1)和(2, 1)，其中第2个递归无效，第1个递归与之前一致，陷入死循环。

1.2 归并排序

也是基于分治，但是有差别，稳定的排序

确定分界点 mid = (l + r) / 2（下标的中间位置）
递归排序left, right
归并——合二为一

时间复杂度$O(nlogn)$

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r){
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    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(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", q[i]);
    return 0;
}

2 二分

2.1 整数

二分的本质不是单调性

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用
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 1;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]使用
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;
    }
}

个人感觉一个特别好的例题：数的范围

理解记忆代码的快速方法：1 2 2 2 3，另外有-1的话mid就需要+1再除以2

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int q[N];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &q[i]);
    }
    while(m--){
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if(q[l] != x) printf("-1 -1\n");
        else {
            printf("%d ", l); // 此处输出的l为最左边x的位置
            int l = 0, r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l); // 此处输出的l为最左边x的位置
        }
    }
    return 0;
}

2.2 浮点数

平方

double bsearch_3(double l, double r){
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    return 0;
}

浮点数二分不需要考虑mid是否+1，else后是否+1。
没有固定的浮点数序列，因此要考虑精度eps，一般比题目要求多1位小数就行
需要自己确定l和r的值，即查找范围

3 高精度

大整数存储：数组，每个元素存一位数字

3.1 高精度加法

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6 + 10;
vector<int> add(vector<int> &A, vector<int> &)

int main(){
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for(auto c:a)
    return 0;
}

3.2 高精度减法

```



## 3.3. 高精度乘法

```c++