09-复杂度与基础算法：二分、排序、双指针¶

目标¶

学会用时间复杂度描述算法大概快慢
会写二分查找（自己写一版）并理解边界
会写 2~3 个经典排序（了解思路），并知道什么时候用 std::sort
学会双指针处理数组/字符串问题

先决知识¶

会用 vector 与 sort/lower_bound（见 07、08 章）

1. 时间复杂度：大概衡量“数据变大后会慢多少”¶

专业名称：时间复杂度（time complexity，常用 Big-O 表示法）
类比：走路：走 10 米和 1000 米差多少；复杂度描述的是“距离变大，耗时怎么变”
作用：比较算法在大数据下的增长趋势（不是精确秒数）
规则/坑点：忽略常数与低阶项，只看增长级别

常见级别（从快到慢，粗略）：

O(1)：常数级（数据多大都差不多）
O(log n)：对数级（二分）
O(n)：线性（遍历一次）
O(n log n)：排序常见
O(n^2)：双重循环（小数据能用，大了会慢）

2. 二分查找：在有序数组里快速定位¶

专业名称：二分查找（binary search）
类比：查字典：先翻中间，看在左边还是右边，再继续一半一半缩小
作用：在有序数组里 O(log n) 查找
规则/坑点：必须有序；边界最容易写错

2.1 自己写一个“找是否存在”的二分（可运行）¶

#include <iostream>
#include <vector>

bool binarySearch(const std::vector<int>& v, int x) {
    int l = 0;
    int r = static_cast<int>(v.size()) - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v[mid] == x) {
            return true;
        } else if (v[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return false;
}

int main() {
    std::vector<int> v = {1, 2, 4, 7, 9, 10};
    int x = 0;
    std::cin >> x;
    std::cout << "exists=" << binarySearch(v, x) << '\n';
    return 0;
}

边界理解（别死背，理解含义）：

这里维护的是闭区间 [l, r]
循环条件 l <= r 表示“区间还有元素”
每次把区间缩小：要么 l = mid + 1，要么 r = mid - 1

2.2 找“第一个 >= x”的位置（对标 lower_bound）¶

#include <iostream>
#include <vector>

int lowerBoundIndex(const std::vector<int>& v, int x) {
    int l = 0;
    int r = static_cast<int>(v.size());
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (v[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int main() {
    std::vector<int> v = {1, 2, 4, 4, 7};
    int x = 0;
    std::cin >> x;
    std::cout << "pos=" << lowerBoundIndex(v, x) << '\n';
    return 0;
}

这里维护的是半开区间 [l, r)，r 可以等于 v.size()，好处是“空区间自然成立”。

3. 排序：把数据按规则排好¶

你真实项目里 99% 应该直接用 std::sort（见 08 章）。但你仍然要理解排序的基本思想，否则你不知道复杂度、也看不懂面试题。

3.1 选择排序（selection sort）：每次选最小¶

思想：第 i 轮在 [i..n-1] 找最小，放到 i
复杂度：O(n^2)

#include <iostream>
#include <vector>

void selectionSort(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (v[j] < v[minIndex]) {
                minIndex = j;
            }
        }
        int t = v[i];
        v[i] = v[minIndex];
        v[minIndex] = t;
    }
}

int main() {
    std::vector<int> v = {5, 1, 4, 2, 3};
    selectionSort(v);
    for (auto x : v) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

3.2 冒泡排序（bubble sort）：把最大的冒到右边¶

思想：不断比较相邻元素，逆序就交换
复杂度：O(n^2)

#include <iostream>
#include <vector>

void bubbleSort(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    for (int i = 0; i < n; i++) {
        bool swapped = false;
        for (int j = 0; j + 1 < n - i; j++) {
            if (v[j] > v[j + 1]) {
                int t = v[j];
                v[j] = v[j + 1];
                v[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

int main() {
    std::vector<int> v = {5, 1, 4, 2, 3};
    bubbleSort(v);
    for (auto x : v) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

理解即可：小数据能用，大了就慢；真正排序请用 std::sort（O(n log n)）。

4. 双指针：两个游标从两头/同向移动¶

专业名称：双指针（two pointers）
类比：两个人从队伍两端往中间走，或者一个走在前面一个跟在后面
作用：很多数组/字符串问题能从 O(n^2) 降到 O(n)
规则/坑点：要维护好不变量（每一步移动必须保持某个条件成立）

4.1 回文判断（可运行）¶

#include <iostream>
#include <string>

bool isPalindrome(const std::string& s) {
    int l = 0;
    int r = static_cast<int>(s.size()) - 1;
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

int main() {
    std::string s;
    std::getline(std::cin >> std::ws, s);
    std::cout << "palindrome=" << isPalindrome(s) << '\n';
    return 0;
}

4.2 有序数组两数之和（可运行）¶

题目：给一个升序数组，找是否存在 a[i] + a[j] == target（i<j）。

#include <iostream>
#include <vector>

bool twoSumSorted(const std::vector<int>& v, int target) {
    int l = 0;
    int r = static_cast<int>(v.size()) - 1;
    while (l < r) {
        int sum = v[l] + v[r];
        if (sum == target) {
            return true;
        } else if (sum < target) {
            l++;
        } else {
            r--;
        }
    }
    return false;
}

int main() {
    std::vector<int> v = {1, 2, 4, 7, 9, 10};
    int target = 0;
    std::cin >> target;
    std::cout << "exists=" << twoSumSorted(v, target) << '\n';
    return 0;
}

逻辑直觉：

和太小就左指针右移（让和变大）
和太大就右指针左移（让和变小）

常见坑¶

错误：二分查找忘记“必须有序”
结果：返回乱值
正确：保证输入有序，或先排序
错误：二分写 mid = (l + r) / 2 并在极端情况下溢出
结果：mid 变负或错乱
正确：用 mid = l + (r - l) / 2
错误：双指针移动没有依据
结果：死循环或漏解
正确：每一步移动都要让目标更接近（维护不变量）

小练习¶

练习 1：手写 lower_bound¶

题目：实现 lowerBoundIndex，并用它判断 x 是否存在
输入/输出：输入 x，输出 pos 与 exists
约束：数组是有序的
提示：见第 2.2 节
目标：把半开区间写熟

练习 2：实现插入排序（理解即可）¶

题目：实现 insertion sort，对 n<=1000 的数据排序
输入/输出：输入 n 和 n 个数，输出排序结果
约束：不用 sort
提示：把当前元素插到左边有序区的正确位置
目标：理解“构造有序区”

练习 3：双指针去重（有序数组）¶

题目：输入一个有序数组，原地去重并输出新长度
输入/输出：输出 newLen
约束：必须 O(n)
提示：慢指针指向“结果末尾”，快指针扫描
目标：训练同向双指针

练习 4：区间合并（排序 + 扫描）¶

题目：输入若干区间 [l,r]，合并重叠区间
输入/输出：输出合并后的区间
约束：先排序再扫
提示：按 l 排序，维护当前合并区间的右端
目标：训练“排序后线性处理”

小结¶

你现在应该掌握：

用 Big-O 粗略判断算法随数据增长的趋势
二分查找的边界写法（闭区间或半开区间）
排序的基本思想与复杂度，实际项目优先 std::sort
双指针能用线性时间解决很多问题

下一篇进入递归与 DFS/BFS：你会学习“树与图”的基本走法。