排序、二分与分治：从“会写”到“会设计”的算法进阶路径

在算法面试中，排序、二分查找与分治策略常被视为“基础题”，但恰恰是这些基础题，最能区分“背过模板”与“真正理解”的候选人。本文以一道经典问题切入，展示如何从排序出发，自然过渡到二分优化，再抽象出分治思想，形成一条完整的解题思维链。

场景引入：从“合并两个有序数组”说起

题目描述：给定两个按非递减顺序排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。请将 nums2 合并到 nums1 中，使合并后的数组同样按非递减顺序排列。nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。

初步思路：最直观的做法是先将 nums2 追加到 nums1 的末尾，然后对整个数组调用 Arrays.sort()。时间开销为 O((m+n)log(m+n))，空间开销为 O(1)（若排序为原地排序）。但这种方法没有利用两个数组“各自有序”这一关键条件，属于“暴力解”。

进阶思路：既然两个数组已经有序，可以借鉴归并排序中“合并”步骤的思想。但若从前往后合并，需要额外数组存储结果；从后往前填充则可以完全利用 nums1 尾部的空闲空间，实现原地合并，时间复杂度降至 O(m+n)。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;      // nums1 有效部分的末尾
    int p2 = n - 1;      // nums2 末尾
    int p = m + n - 1;   // 合并后数组的末尾

    // 从后往前比较，较大者放入 nums1 的末尾
    while (p2 >= 0) {    // 只需处理 nums2 剩余元素，nums1 剩余部分自然有序
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p--] = nums1[p1--];
        } else {
            nums1[p--] = nums2[p2--];
        }
    }
}

关键点：while (p2 >= 0) 而非 while (p1 >= 0 || p2 >= 0)，因为当 p2 < 0 时，nums1 的前 p+1 位已是有序的，无需继续操作。容易踩坑的是忘记 p1 >= 0 的判断，若 nums1 的有效部分先耗尽，会尝试访问负索引。时间复杂度 O(m+n)，空间复杂度 O(1)。

二分查找：从“找值”到“找边界”的思维跃迁

合并问题解决后，自然延伸出一个更著名的面试题：LeetCode 4. 寻找两个正序数组的中位数。要求时间复杂度为 O(log(m+n))。若沿用合并思路，合并后取中位数已是 O(m+n)，无法满足要求。此时，二分查找便登场了。

核心洞察：中位数的本质是将数组分为左右两半，使左半最大值 ≤ 右半最小值，且左半元素个数与右半元素个数相等（或相差 1）。对于两个数组，可以对较短的数组进行二分，确定分割位置后，另一个数组的分割位置由元素总数推导得出。若分割满足交叉大小关系（nums1[leftMax] ≤ nums2[rightMin] 且 nums2[leftMax] ≤ nums1[rightMin]），则已找到中位数；否则根据大小关系调整二分方向。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // 保证 nums1 是较短数组，减少二分次数
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    int m = nums1.length, n = nums2.length;
    int totalLeft = (m + n + 1) / 2;  // 左半部分元素总数
    int left = 0, right = m;

    while (left < right) {
        int i = left + (right - left) / 2;  // nums1 左半元素个数
        int j = totalLeft - i;              // nums2 左半元素个数
        if (nums1[i] < nums2[j - 1]) {
            // nums1 左半太小，需要右移分割线
            left = i + 1;
        } else {
            right = i;
        }
    }

    int i = left, j = totalLeft - i;
    // 处理边界：分割线在数组最左或最右时，对应值为极值
    int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
    int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
    int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
    int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

    if ((m + n) % 2 == 1) {
        return Math.max(nums1LeftMax, nums2LeftMax);  // 奇数个，取左半最大值
    } else {
        // 偶数个，取左半最大值与右半最小值的平均
        return (Math.max(nums1LeftMax, nums2LeftMax)
              + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
    }
}

关键点：二分对象是“较短数组的分割位置”，而非直接找中位数值。totalLeft 的取整方式确保了奇数长度时中位数落在左半。容易踩坑：比较条件 nums1[i] < nums2[j-1] 中，索引 j-1 可能为 -1（当 j=0 时），因此需要确保 nums1 为较短数组，且二分边界 right = m 避免 i = m 时访问 nums1[m]。时间复杂度 O(log(min(m,n)))，空间复杂度 O(1)。

分治思想：从“具体算法”到“通用方法论”

上述两题虽解法不同，但底层共享同一方法论：分治。合并有序数组是“分治”中“治”的部分——将两个已排序子问题结果合并；二分查找是“分”的极致——每次将问题规模减半。分治的通用框架为：分解 → 解决 → 合并。LeetCode 53. 最大子数组和 是检验分治理解程度的经典题。

题目描述：给定整数数组 nums，找出具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路推导：暴力解枚举所有子数组需 O(n²)。贪心或动态规划可将复杂度降至 O(n)，但分治提供了另一种视角：将数组从中点分为左右两半，最大子数组要么完全在左半，要么完全在右半，要么跨越中点。前两种情况递归求解，第三种情况需从中点向两侧扩展，计算包含中点的最大和。

public int maxSubArray(int[] nums) {
    return divide(nums, 0, nums.length - 1);
}

private int divide(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];  // 单个元素直接返回
    }
    int mid = left + (right - left) / 2;
    // 递归求解左右两半的最大子数组和
    int leftMax = divide(nums, left, mid);
    int rightMax = divide(nums, mid + 1, right);

    // 计算跨越中点的最大和：从中点向左扩展 + 从中点向右扩展
    int leftCrossMax = Integer.MIN_VALUE, rightCrossMax = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--) {   // 向左扩展，寻找最大后缀和
        sum += nums[i];
        leftCrossMax = Math.max(leftCrossMax, sum);
    }
    sum = 0;
    for (int i = mid + 1; i <= right; i++) { // 向右扩展，寻找最大前缀和
        sum += nums[i];
        rightCrossMax = Math.max(rightCrossMax, sum);
    }
    int crossMax = leftCrossMax + rightCrossMax;

    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

关键点：跨中点的最大和必须包含 nums[mid] 和 nums[mid+1]，因此从两个方向分别扩展时均以中点邻接位置为起点。容易踩坑：递归终止条件必须是 left == right 而非 left > right，否则空数组情况会导致错误。时间复杂度 O(n log n)（每层合并需 O(n)），空间复杂度 O(log n)（递归栈深度）。

延伸与对比：何时选择分治而非线性扫描？

对最大子数组和，分治并非最优解（动态规划 O(n) 更优），但它的价值在于揭示问题结构。面试中，若候选人能主动指出“分治解法虽不是最优，但体现了对问题分解的思考”，往往比直接背诵动态规划代码更能体现思维深度。类似题还包括 LeetCode 215. 数组中的第K个最大元素（可用分治思想的快速选择，平均 O(n)），以及 LeetCode 148. 排序链表（归并排序的链表实现，体现分治在链式结构中的应用）。

总结与行动建议

回顾三条解题路径：合并数组展示了“利用已知有序条件”的优化意识；找中位数将二分从“查找”升维到“划分边界”；最大子数组和则展现了分治作为通用方法论的价值。三者层层递进，共同指向算法面试的核心考察点——不是记忆模板，而是识别问题的结构特征，选择合适的分解策略。

下一步行动建议：选取上述三道题（LeetCode 88、4、53）独立重写代码，并尝试用英文口述解题思路。随后挑战 LeetCode 215 与 148，对比快速选择与快速排序的异同，以及归并排序在数组与链表上的实现差异。每次练习后，用一句话总结“这道题为什么适合用这种策略”，积累属于自己的解题决策树。

本文关键词：二分查找、分治、归并排序、LeetCode 4、LeetCode 53