算法基础课

/**
1. 初始化一个x，从序列中选择q[l] or q[l+r >>1] or q[r]
2. 调整区间，左边都小于x, 右边都大于x。
3. 递归左边和右边，quicksort(q, l, j) quicksort(q, j+1, 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); // 这个check condition没有=，[0,2,3,2,4]假设取到x=2，先do，可以越过=2的状态。
        do j --; while(q[j] > x); // 而且停止循环时，i指向3，j指向2（第一个）。即，i=2,j=1。
        if(i < j) swap(q[i], q[j]);
    } // 退出循环两种情况：i==j ; i=j+1
    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]); // printf记得在d后面留个空格
    return 0;
}

/**
1. 确定分界点 mid=(l+r) / 2
2. 递归排序left, right
3. 归并，合二为一
**/

#include <iostream>

using namespace std;

const int N = 1e6+10;

int n;
int q[N], temp[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); //递归后的代码面对的是排序好的序列，在递归中，左l,右r。
    int k = 0, i = l, j = mid + 1;
    while(i<=mid && j<=r)
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else temp[k++]=q[j++];
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[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;
}

/**
作者：Aikedaer
链接：https://www.acwing.com/activity/content/code/content/6032937/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
**/

#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(x<=q[mid]) r = mid; // 虽然可能有很多x，但找左边界时只需要盯住那一个就可以了。
            else l = mid + 1;
        }
        if(q[l]!=x) cout << "-1 -1" << endl;
        else{
            cout << l << " ";
            int l = 0, r = n - 1;
            while(l<r){
                int mid = l + r + 1 >> 1;
                if(x>=q[mid]) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }

}