python/TangDou/AcWing/BinarySearch/插入二分排序.md

### 一、$STL$版本的插入二分排序
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 6;
int a[N] = {3, 2, 1, 4, 5, 7};

void BinInsertSort(int a[], int n) {
    for (int i = 1; i < n; i++) { // 把下标0的没处理，做为基础数据，其它的一个个做二分插入排序
        int x = a[i];             // 辅助变量x用来保存待排序的元素,因为后面有整体移动的过程，不单独记下来，后面就被改了
        // 这个代码其实很巧妙的，一个数组分两半用，一半是待插入的，另一个是插入完的，牛啊！
        int pos = lower_bound(a, a + i, x) - a;             // 在a数组中，范围[0,a+i)这个前闭后开的区间内查找第一个大于等于x的位置p
        for (int j = i - 1; j >= pos; j--) a[j + 1] = a[j]; // 移动元素，腾出空间,将pos位置倒出来
        a[pos] = x;                                         // 将待排序的元素插入
    }
}

int main() {
    // 插入排序+二分
    BinInsertSort(a, N);
    for (int i = 0; i < N; i++) printf("%d ", a[i]);
    return 0;
}
```

### 二、手写二分版本的插入二分排序
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 6;
int a[N] = {3, 2, 1, 4, 4, 7};

void BinInsertSort(int a[], int n) {
    for (int i = 1; i < n; i++) { // 把下标0的没处理，做为基础数据，其它的一个个做二分插入排序
        int x = a[i];             // 辅助变量x用来保存待排序的元素,因为后面有整体移动的过程，不单独记下来，后面就被改了
        // 这个代码其实很巧妙的，一个数组分两半用，一半是待插入的，另一个是插入完的，牛啊！

        // 手写二分lower_bound模板,左闭右开
        int l = 0, r = i; //[0~i-1] <=> [0,i)
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        // 此处写l,r都是一样的
        for (int j = i - 1; j >= r; j--) a[j + 1] = a[j]; // 移动元素，腾出空间,将pos位置倒出来
        a[r] = x;                                         // 将待排序的元素插入
    }
}

int main() {
    // 插入排序+二分
    BinInsertSort(a, N);
    for (int i = 0; i < N; i++) printf("%d ", a[i]);
    return 0;
}
```