【算法设计与分析】（三）二分搜索技术与大整数乘法

---

前言

• 在上一篇博客中，我们已深入剖析了递归的本质内涵与分治法的核心思想 —— 通过将复杂问题分解为规模更小的子问题，逐步求解后合并结果。
• 本文将延续这一思路，聚焦分治策略在两大经典算法场景中的精妙应用：二分搜索技术与大整数乘法，揭示其如何通过 “分而治之” 的智慧突破传统算法的效率瓶颈。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的算法与设计博客专栏
https://blog.csdn.net/2402_83322742/category_12903664.html?spm=1001.2014.3001.5482

---

一、二分搜索技术

1. 为什么需要二分搜索？

想象你有一本按拼音排序的字典，现在要找"苹果"这个词。如果一页页翻（线性搜索），最坏要翻几百页。但如果每次从中间翻开：

• 中间是"葡萄"，说明"苹果"在前面半本
• 再翻前半本的中间，是"香蕉"，说明在香蕉后面
• 重复这个过程，很快就能找到

核心条件：数据必须是有序的（升序/降序排列），就像排好序的字典、成绩单、商品价格列表等。

2. 二分搜索怎么做？

记住三个指针：左边界（left）、右边界（right）、中间位置（mid）

步骤分解：

假设有序数组：[1,3,5,7,9]，目标是找7

1. 初始化：left=0（第一个元素），right=4（最后一个元素）

2. 循环条件：left ≤ right（还有范围没查完）

3. 每次循环：

   • 计算中间位置：mid = (left + right) // 2 （整数除法，这里mid=2，对应元素5）
   • 比较中间元素和目标：
     • 5 < 7 → 目标在右半部分，left=mid+1（left=3）
   • 新范围：left=3，right=4，mid=(3+4)//2=3，对应元素7
   • 找到目标，返回位置3

3. 为什么说它很快？

假设数组有1000个元素：

• 线性搜索最坏要找1000次
• 二分搜索最多找多少次？每次砍半：
  1000→500→250→125→62→31→15→7→3→1，总共10次左右

数学公式：时间复杂度O(log₂n)，n是数据量。log₂1000≈10，log₂1000000≈20，无论数据多大，搜索次数都是几十次以内，比线性搜索的O(n)快很多。

4. 哪些场景会用到？

• 电商平台：搜索某价格区间的商品（后台用二分快速定位）
• 考试查分：输入准考证号快速定位成绩（数据提前排序）
• 代码调试：找数组中是否存在某个错误代码（先排序再搜索）

二、大整数乘法

1. 问题来了：数字太大怎么办？

假设要计算：

9999999999999999 × 8888888888888888

• 普通计算器直接显示"ERROR"（超过位数限制）
• 电脑里的整数类型（如Python的int虽然能存大整数），但传统乘法效率很低

核心问题：当数字位数n很大时（比如n=1000位），传统乘法的计算量会爆炸，需要更聪明的算法。

2. 传统方法

计算123×456：

    123× 456------738  （123×6）6150  （123×50，注意错位）49200  （123×400，注意错位）------56088

计算逻辑：每一位相乘后错位相加，总共有n×m次乘法（n和m是两个数的位数），时间复杂度O(n²)。当n=1000时，需要约100万次运算，还能接受；但n=10000时，需要1亿次，开始变慢。

3. 用分治思想优化

假设两个n位的数X和Y（n是偶数，方便拆分）：

• X拆成高位A和低位B：X = A×10^(n/2) + B （比如X=1234，A=12，B=34，1234=12×100+34）
• Y拆成高位C和低位D：Y = C×10^(n/2) + D
• 那么X×Y = (A×10^{(n/2)+B)(C×10}(n/2)+D) = AC×10^n + (AD+BC)×10^(n/2) + BD

关键优化：AD+BC可以写成(A+B)(C+D) - AC - BD，这样原来的4次乘法（AC、AD、BC、BD）变成3次乘法（AC、BD、(A+B)(C+D)），减少计算量。

4. Karatsuba算法：具体怎么算？

计算1234×5678：

1. 拆分成n=2位的A=12, B=34；C=56, D=78
2. 计算三个子问题：
   • AC = 12×56 = 672
   • BD = 34×78 = 2652
   • (A+B)(C+D) = (12+34)×(56+78)=46×134=6164
3. 计算中间项：6164 - 672 - 2652 = 2840
4. 组合结果：

   AC×10^4 = 672×10000 = 6720000
   中间项×10^2 = 2840×100 = 284000
   BD = 2652
   总和：6720000 + 284000 + 2652 = 7006652
   

   实际计算1234×5678=7006652，结果正确！

5. 效率提升有多大？

• 传统方法：O(n²)，n=1000时运算量1,000,000次
• Karatsuba算法：O(n^{1.585)，n=1000时运算量约1000}1.585≈300,000次，快了3倍多
• 当n更大（如n=1,000,000），差距会指数级扩大

6. 实际应用场景

• 密码学：RSA加密需要计算非常大的整数乘法（几千位到几万位）
• 科学计算：天文数据、量子模拟中的超大数运算
• 编程语言底层：Python、Java等支持大整数运算的语言，内部就用了类似算法优化

总结

• 二分搜索：利用有序性，每次砍半缩小范围，把O(n)的问题变成O(log n)
• 大整数乘法：用分治思想把大数拆小数，减少乘法次数，把O(n²)优化到O(n^1.585)

---

以上就是对本次博客所有内容，后续我们将深入探讨算法与设计更多知识。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的算法与设计博客专栏
https://blog.csdn.net/2402_83322742/category_12903664.html?spm=1001.2014.3001.5482

非常感谢您的阅读，喜欢的话记得三连哦