算法课堂笔记

核心内容：二分查找 + 归并排序（逆序对）

目录

1. 二分查找（Binary Search）
   • 核心思想与前提
   • 7类经典二分查找场景
   • 二分答案（扩展应用）
2. 归并排序（Merge Sort）
   • 核心思想
   • 实现代码与解析
3. 逆序对统计（归并排序扩展）
   • 逆序对定义
   • 统计逻辑与代码
4. 快速排序（思路）
5. 核心要点总结

---

1. 二分查找（Binary Search）

1.1 核心思想

二分查找是在有序数组中通过不断缩小搜索范围（每次排除一半元素）实现高效查找的算法，时间复杂度为 $O(logn)$。核心是通过 mid = l + r >> 1（等价于 $(l+r)/2$，位运算更高效）划分区间，根据条件调整左右边界。

1.2 前提条件

• 数组必须是有序的（以下示例均基于升序数组）；
• 数组下标从1开始（代码中默认设定）；
• 基础变量定义：int n, a[1000010];（n为数组长度，a为有序数组）。

1.3 7类经典二分查找场景

场景编号	功能描述	函数名	核心逻辑	返回值说明
1	查找数字k是否存在	bs(k)	找到k返回1，否则调整区间	存在返回1，不存在返回0
2	查找k第一次出现的位置	bs2(k)	找到k时记录位置，向左继续搜索	找到返回位置，否则返回0
3	查找k最后一次出现的位置	bs3(k)	找到k时记录位置，向右继续搜索
4	查找大于k的第一个位置	bs4(k)	找到>k的值时记录位置，向左搜索
5	查找≥k的第一个位置	bs5(k)	找到≥k的值时记录位置，向左搜索
6	查找小于k的最后一个位置	bs6(k)	找到<k的值时记录位置，向右搜索
7	查找≤k的最后一个位置	bs7(k)	找到≤k的值时记录位置，向右搜索

场景1：查找数字k是否存在

int bs(int k){
    int l = 1, r = n;
    while (l <= r){
        int mid = l + r >> 1;
        if (a[mid] == k) return 1; // 找到k直接返回
        if (a[mid] > k) r = mid - 1; // k在左半区
        if (a[mid] < k) l = mid + 1; // k在右半区
    }
    return 0; // 未找到
}

场景2：查找k第一次出现的位置

int bs2(int k){
    int l = 1, r = n, ans = 0; // ans记录目标位置
    while (l <= r){
        int mid = l + r >> 1;
        if (a[mid] == k) ans = mid, r = mid - 1; // 找到后向左找更早的位置
        if (a[mid] > k) r = mid - 1;
        if (a[mid] < k) l = mid + 1;
    }
    return ans; // 未找到返回0
}

场景3：查找k最后一次出现的位置

int bs3(int k){
    int l = 1, r = n, ans = 0;
    while (l <= r){
        int mid = l + r >> 1;
        if (a[mid] == k) ans = mid, l = mid + 1; // 找到后向右找更晚的位置
        if (a[mid] > k) r = mid - 1;
        if (a[mid] < k) l = mid + 1;
    }
    return ans;
}

场景4：查找大于k的第一个位置（修正原代码笔误）

int bs4(int k){
    int l = 1, r = n, ans = 0;
    while (l <= r){
        int mid = l + r >> 1; // 原代码误写为m，已修正
        if (a[mid] > k) ans = mid, r = mid - 1; // 向左找更早的大于k的位置
        else l = mid + 1;
    }
    return ans;
}

场景5：查找≥k的第一个位置（修正原代码笔误）

int bs5(int k){
    int l = 1, r = n, ans = 0;
    while (l <= r){
        int mid = l + r >> 1; // 原代码误写为m，已修正
        if (a[mid] >= k) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

场景6：查找小于k的最后一个位置

int bs6(int k){
    int l = 1, r = n, ans = 0;
    while (l <= r){
        int mid = l + r >> 1;
        if (a[mid] < k) ans = mid, l = mid + 1; // 向右找更晚的小于k的位置
        else r = mid - 1;
    }
    return ans;
}

场景7：查找≤k的最后一个位置

int bs7(int k){
    int l = 1, r = n, ans = 0;
    while (l <= r){
        int mid = l + r >> 1;
        if (a[mid] <= k) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

1.4 二分答案（扩展应用）

核心思想

用于求解“满足条件的最大/最小值”问题，核心是定义check函数判断当前值是否满足条件，通过二分调整边界找到最优解。

示例：分割数组得到至少m份的最大长度

// 检查长度x是否能分割出至少m份
bool check(int x){
    int res = 0;
    for (int i = 1; i <= n; i++) res += a[i] / x;
    return res >= m;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1e9, ans;
    while (l <= r){
        int mid = l + r >> 1;
        if (check(mid)){
            ans = mid; // 满足条件，记录当前值
            l = mid + 1; // 尝试更大值
        } else {
            r = mid - 1; // 不满足，尝试更小值
        }
    }
    cout << ans;
    return 0;
}

---

2. 归并排序（Merge Sort）

2.1 核心思想

基于分治思想，将数组拆分为若干子数组分别排序，再将有序子数组合并为整体有序数组，时间复杂度稳定为 $O(nlogn)$，适合大规模数据排序。

2.2 实现代码与解析

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

// 对a[l..r]进行升序排序
void guibing(int l, int r){
    if (l >= r) return; // 递归终止：单个元素无需排序
    int mid = l + r >> 1;
    guibing(l, mid); // 排序左半区间[l, mid]
    guibing(mid + 1, r); // 排序右半区间[mid+1, r]
    
    // 合并两个有序子数组
    int c[r - l + 10], cnt = 0; // 临时数组存储合并结果
    int p1 = l, p2 = mid + 1; // 双指针分别指向左右区间起点
    while (p1 <= mid && p2 <= r){
        if (a[p1] < a[p2]) c[++cnt] = a[p1++];
        else c[++cnt] = a[p2++];
    }
    // 处理剩余元素
    while (p1 <= mid) c[++cnt] = a[p1++];
    while (p2 <= r) c[++cnt] = a[p2++];
    // 复制回原数组
    for (int i = l; i <= r; i++) a[i] = c[i - l + 1];
}

---

3. 逆序对统计（归并排序扩展）

3.1 逆序对定义

数组中满足 $i < j$ 且 $a[i] > a[j]$ 的数对，归并排序可在 $O(nlogn)$ 时间内统计数量。

3.2 统计逻辑

逆序对数量分为三部分：

1. 左半区间 $[l, mid]$ 的逆序对数量；
2. 右半区间 $[mid+1, r]$ 的逆序对数量；
3. 跨左右区间的逆序对数量（合并时统计）。

3.3 实现代码与解析

// 排序a[l..r]（降序）并返回该区间逆序对数量
int nxd(int l, int r){
    if (l >= r) return 0; // 递归终止：无逆序对
    int ans = 0, mid = l + r >> 1;
    ans += nxd(l, mid); // 统计左区间逆序对
    ans += nxd(mid + 1, r); // 统计右区间逆序对
    
    // 合并并统计跨区间逆序对
    int c[r - l + 10], cnt = 0;
    int p1 = l, p2 = mid + 1;
    while (p1 <= mid && p2 <= r){
        if (a[p1] > a[p2]){
            // 右区间剩余元素都与a[p1]构成逆序对
            ans += r - p2 + 1;
            c[++cnt] = a[p1++];
        } else {
            c[++cnt] = a[p2++];
        }
    }
    // 处理剩余元素
    while (p1 <= mid) c[++cnt] = a[p1++];
    while (p2 <= r) c[++cnt] = a[p2++];
    // 复制回原数组
    for (int i = l; i <= r; i++) a[i] = c[i - l + 1];
    return ans;
}

// 主函数调用
signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << nxd(1, n); // 输出整个数组的逆序对数量
    return 0;
}

---

4. 快速排序（思路）

4.1 核心思想

基于分治思想，选取“参照物（czw）”将数组分为“小于/等于/大于”三部分，递归排序前、后两部分，平均时间复杂度 $O(nlogn)$。

4.2 核心框架

void qp(int l, int r){
    if (l >= r) return; // 递归终止
    int czw = a[l]; // 选取左端点作为参照物
    // 分区逻辑：
    // 1. 小于参照物的元素放左侧
    // 2. 等于参照物的元素放中间
    // 3. 大于参照物的元素放右侧
    // 递归排序“小于”和“大于”的区间
}

---

5. 核心要点总结

5.1 二分查找

1. 核心前提是数组有序，二分答案需先定义check函数判断条件；
2. 注意下标边界（如数组从1开始）和变量名笔误（如m应为mid）；
3. mid = l + r >> 1 是位运算优化，大数场景可改为l + (r-l)/2避免溢出。

5.2 归并排序 & 逆序对

1. 归并排序核心是“分治+合并”，需用临时数组存储合并结果避免数据覆盖；
2. 跨区间逆序对数量可通过r - p2 + 1快速计算；
3. 递归终止条件均为l >= r（单个元素无需处理）。

5.3 通用技巧

1. 数组下标从1开始时，合并结果复制需注意c[i - l + 1]的偏移量；
2. 二分查找/归并排序的时间复杂度均为 $O(logn)$ 或 $O(nlogn)$，远优于暴力遍历。