Divide and Conquer

Quick Sort (快速排序)

int a[Z];
void quick_sort(int l, int r) {
    int i = l, j = r, mid = a[(l + r) >> 1]; //基准存值而不是下标（交换会移动a[mid]）
    while (i <= j) { //等号不能少
        while (a[i] < mid) i++; //左半寻找不小于mid的（用<=会越界）
        while (a[j] > mid) j--; //右半寻找不大于mid的
        if (i <= j) swap(a[i++], a[j--]); //交换大小，使得mid左边都小于mid，右边都大于mid
    }
    if (i < r) quick_sort(i, r); //区间边界
    if (j > l) quick_sort(l, j);
}

Merge Sort (归并排序)

$O(n \log n)$, 稳定排序算法，适合链表排序和大数据排序（外部排序）。

int a[Z], b[Z];
void merge_sort(int l, int r) {
    if (l >= r) return; //base case
    int mid = (l + r) >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) { //排序
        if (a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }
    while (i <= mid) b[k++] = a[i++]; //左剩余
    while (j <= r) b[k++] = a[j++]; //右剩余
    for (int u = l; u <= r; u++)  a[u] = b[u]; //剩余转移
}

Binary Exponentiation (快速幂)

//a底数，b指数，c取模数
int binpow(int a, int b, int c) {
    int res = 1 % c; //c = 1 时结果为 0
    a = a % c; //防止a过大
    while (b) {
        if (b & 1) res = res * a % c; //奇数补一项
        a = a * a % c;
        b >>= 1;
    }
    return res;
}

Binary Search (二分查找)

数组有序

int binary_search(int l, int r, int aim) {
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (a[mid] > aim) r = mid - 1;
        else if (a[mid] < aim) l = mid + 1;
        else ans = mid, r = mid - 1; //找到后继续向左，得到最左边的aim
    }
    return ans;
}

Karatsuba Multiplication

• Input: two $n$-digit big numbers $X$ and $Y$.
• Output: the product $Z = X \cdot Y$.

Core idea: reduce the number of multiplications from 4 to 3.

Algorithm:

1. Split $X$ and $Y$ into two halves: $m = \lfloor \frac{n}{2} \rfloor$.
   • $X = X_l \cdot 10^{m} + X_r$
   • $Y = Y_l \cdot 10^{m} + Y_r$
   • $Z = (X_l Y_l) \cdot 10^{2m} + (X_l Y_r + X_r Y_l) \cdot 10^{m} + (X_r Y_r)$
2. Compute three products recursively:
   • $P_1 = X_l \cdot Y_l$
   • $P_2 = X_r \cdot Y_r$
   • $P_3 = (X_l + X_r) \cdot (Y_l + Y_r)$
3. Combine the results: $Z = P_1 \cdot 10^{2m} + (P_3 - P_1 - P_2) \cdot 10^{m} + P_2$

$T(n) = 3T(\frac{n}{2}) + O(n)$.
$O(n^{\log_2 3})$, faster than the traditional $O(n^2)$ algorithm.

int karatsuba(int X, int Y) {
    if (X < 10 || Y < 10) return X * Y; // base case
    int m = max(to_string(X).size(), to_string(Y).size()) / 2;
    int power = pow(10, m);
    int Xl = X / power, Xr = X % power;
    int Yl = Y / power, Yr = Y % power;
    int P1 = karatsuba(Xl, Yl);
    int P2 = karatsuba(Xr, Yr);
    int P3 = karatsuba(Xl + Xr, Yl + Yr);
    return P1 * power * power + (P3 - P1 - P2) * power + P2;
}

Toom-Cook Multiplication

Split the numbers into $k$ parts

$O(n^{\log_k (2k - 1)})$.

k-th Rank Selection (第k小数)

• Input: an array $A$ of $n$ numbers and an integer $k$.
• Output: the $k$-th smallest number in $A$.

Steps:

1. Randomly select a pivot $p$ from $A$.
2. Partition $A$ into three parts:
   • $A_1 = \{x \in A | x < p\}$
   • $A_2 = \{x \in A | x = p\}$
   • $A_3 = \{x \in A | x > p\}$
3. If $|A_1| \geq k$, the $k$-th smallest number is in $A_1$.
4. If $|A_1| + |A_2| \geq k$, the $k$-th smallest number is $p$.

int kth_rank(int l, int r, int k) {
    if (l == r) return a[l]; // base case
    int pivot = a[rand() % (r - l + 1) + l]; //随机选取一个数作为pivot
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }
    if (k <= j - l + 1) return kth_rank(l, j, k);
    else if (k > i - l) return kth_rank(i, r, k - (i - l));
    else return pivot;
}

Closest Pair of Points (最近点对)

Complexity: $O(n \log n)$ (sorting the strip at every level as below gives $O(n \log^2 n)$). Sort points[l..r] by $x$ before the first call.

Steps:

1. Sort the points by their x-coordinates.
2. Divide the points into two halves.
3. Recursively find the closest pair in each half.
4. Find the closest pair that straddles the dividing line.
5. Use a strip of width $2d$ centered on the dividing line, where $d$ is the minimum distance found in the two halves.
6. For each point in the strip, check only the next 7 points in the sorted order by y-coordinate to find the closest pair.

struct Point {
    int x, y;
};
Point points[Z];
double closest_pair(int l, int r) {
    if (r - l <= 3) { // base case
        double min_dist = DBL_MAX;
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j <= r; j++) {
                double dist = sqrt(pow(points[i].x - points[j].x, 2) + pow(points[i].y - points[j].y, 2));
                min_dist = min(min_dist, dist);
            }
        }
        return min_dist;
    }
    int mid = (l + r) / 2;
    double d1 = closest_pair(l, mid);
    double d2 = closest_pair(mid + 1, r);
    double d = min(d1, d2);

    vector<Point> strip;
    for (int i = l; i <= r; i++) {
        if (abs(points[i].x - points[mid].x) < d) {
            strip.push_back(points[i]);
        }
    }
    sort(strip.begin(), strip.end(), [](const Point &a, const Point &b) { return a.y < b.y; });

    for (size_t i = 0; i < strip.size(); i++) {
        for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d; j++) {
            double dist = sqrt(pow(strip[i].x - strip[j].x, 2) + pow(strip[i].y - strip[j].y, 2));
            d = min(d, dist);
        }
    }
    return d;
}