波仔
💻 第六章 与数据结构成为好朋友的七个要点
📄 一句话概括

第五章的典型算法几乎全跑在数组上：线性查找、二分查找、冒泡排序——数组是典型算法的舞台。

📝 本节和前面几节的关系

第五章学算法、本章学结构，这一节把两者接起来：算法离不开结构的舞台。

一、回看典型算法的舞台

线性查找：按下标 0、1、2… 挨个比——数组遍历； 二分查找：前提【数组有序】，取中位比较砍一半——没有下标直达就玩不转； 冒泡排序：相邻下标的元素两两交换——还是数组。 第五章的招式库，几乎每一招都默认舞台是数组。

二、二分查找：数组＋有序的组合拳

二分查找的每一步都依赖【按任意下标一步直达】——这正是数组独有的本领（链表就只能顺藤摸瓜）。 10 个元素 3 步命中、100 万个 20 步、10 亿个 30 步——对数级的威力建立在【数组＋有序】之上。 所以【数据结构的选择】直接决定【算法能多快】——这就是本章标题【与数据结构成为好朋友】的深意。

三、舞台与戏的比喻

算法是戏，数据结构是舞台：换舞台，同一出戏就演不了（链表上演不了二分）； 选舞台前先问：这出戏要什么？（随机访问？快速插删？先进先出？）——下一节把四种典型舞台排成一排供你挑。

四、动手 Demo：有序数组上的二分查找

在 10 格有序数组里找 23，每一步砍一半。

# 二分查找: 数组 + 有序 = 对数级速度
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
lo, hi, t = 0, len(arr) - 1, 23
while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == t:
        print("命中下标", mid)
        break
    elif arr[mid] < t:
        lo = mid + 1
    else:
        hi = mid - 1

实跑输出：

--------------------------------------------------------------------
要点 3——数组的应用：二分查找
--------------------------------------------------------------------

第四章的典型算法，几乎都跑在数组上。最有代表性的是二分查找：
**前提数组有序**，每次与中位比较，砍掉一半。

有序数组: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    第 1 步: 中位下标 4 值 16 太小 -> 查右半 [5..9]
    第 2 步: 中位下标 7 值 56 太大 -> 查左半 [5..6]
    第 3 步: 中位下标 5 值 23 -> 命中 23!

10 个元素 3 步命中; 100 万个元素也只要 20 步——
这就是【数组＋有序】这对组合的威力。
数组是舞台上最常用的数据结构：线性查找、二分查找、冒泡排序（4.7/5.8）全都以它为主角。

把数组换成乱序再跑——结果不可靠，因为二分的前提【有序】被破坏了。 线性查找对乱序数组照样工作——查找算法的选型取决于【数据是否有序】。

30 秒实验

  1. 在 100 万格有序数组里二分，最多 20 步——用对数心算验证（2^20 约一百万）。
  2. 想一个链表上没法做二分的理由（提示：链表没有下标直达）。

常见误区

  1. 以为二分查找什么数组都能用——前提是有序，乱序数组二分会漏目标。
  2. 以为换数据结构不影响算法——舞台换了，戏就得重排。
自测三问（点开对答案） 1. 为什么典型算法偏爱数组？ —— 按下标一步直达＋连续存放，正是大多数算法的运行前提。 2. 二分查找的两个前提是什么？ —— 数组（可随机访问）＋已排序。 3. 100 万元素二分最多几步？ —— 20 步（2 的 20 次方约 100 万）。

相关笔记