---
marp: true
theme: kurzus
paginate: true
footer: 数据结构 · 第 2 周 · 效率、查找
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# 数据结构

## 第 2 周 – 算法的效率，顺序查找与二分查找

Koczka Ferenc 博士 · 埃斯特哈齐·卡罗伊大学 · 2026

---

## 复习

- <strong>算法：</strong>有限的、定义明确的步骤序列
- <strong>数据类型：</strong>值的集合 + 运算 + 表示
- <strong>数据结构：</strong>元素 + 关系 + 操作
- 访问方式：<strong>直接</strong>（数组） · <strong>顺序</strong>（链表）

### 今天的问题

- 怎样判断一个算法是<strong>快</strong>还是<strong>慢</strong>？
- 怎样在数组中找到一个元素 – 能不能找得<strong>更快</strong>？

<!--
时间安排：复习 5' · 效率、大O 40' · 顺序查找 15' · 二分查找 25' · 小结 5'
-->

---

<!-- _class: fejezet -->

# 算法的效率

---

## 为什么只用秒表不够？

运行时间取决于

- 机器（处理器、内存），
- 编程语言和编译器，
- 同时运行的其他程序，
- <strong>输入的规模和内容</strong>。

<div class="doboz">

因此我们不以秒为单位来衡量，而是考察<strong>步数</strong>如何随<strong>输入规模（n）</strong>增长。

</div>

<strong>步（基本操作）：</strong>赋值、比较、算术运算、访问数组元素 – 各算作一步。

---

## 计算步数：一个例子

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码 – 求和</span>

```text
Function Sum(A, n)
  s ← 0                      // 1
  For i ← 1 to n             // n 次
    s ← s + A[i]             // n
  End for
  Return s                   // 1
End function
```

</div>
<div>

- 赋值和返回：<strong>常数</strong>步
- 循环体执行 <strong>n</strong> 次
- 总共约 <strong>c₁ · n + c₂</strong> 步

<div class="doboz tipp">

常数（c₁、c₂）取决于机器 – 重要的是步数随 n <strong>线性</strong>增长。

</div>

</div>
</div>

---

## 最好、最坏和平均情况

即使输入规模相同，步数也可能不同！

<strong>例：</strong>在 <em>n</em> 个元素的数组中从前往后查找值 `x`。

| 情况 | 何时？ | 步数 |
|---|---|---|
| <strong>最好</strong> | `x` 是第一个元素 | 1 |
| <strong>最坏</strong> | `x` 是最后一个，或者不在数组中 | n |
| <strong>平均</strong> | `x` 出现在各位置的可能性相同 | 约 n / 2 |

<div class="doboz">

通常我们考察<strong>最坏情况</strong>：它是一种保证 – 肯定不会比这更慢。

</div>

---

## 增长速度

![w:820](kepek/h02_novekedes.svg)

---

<!-- _class: kicsi -->

## 实际需要多长时间？

假设机器每秒执行 <strong>10⁹ 步</strong>。

| n | log₂ n | n | n · log₂ n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10 | 3 ns | 10 ns | 33 ns | 100 ns | 1 µs |
| 1 000 | 10 ns | 1 µs | 10 µs | 1 ms | ∞（≈ 10²⁸⁴ 年） |
| 10⁶ | 20 ns | 1 ms | 20 ms | <strong>17 分钟</strong> | ∞ |
| 10⁹ | 30 ns | 1 s | 30 s | <strong>32 年</strong> | ∞ |

<div class="doboz figyelem">

更快的机器几乎没有帮助：<strong>快 10 倍</strong>的机器只是把 32 年变成 3.2 年。出路在于<strong>更好的算法</strong>。

</div>

---

## 大O记号

<strong>直观地说：</strong>如果 <em>f</em> 的增长至多和 <em>g</em> 一样快（忽略常数因子），就写作 `f(n) = O(g(n))`。

<strong>精确地说：</strong>`f(n) = O(g(n))`，如果存在常数 <em>c</em> > 0 和 <em>n₀</em>，使得

> 对所有 n ≥ n₀，有 f(n) ≤ c · g(n)。

<strong>规则：</strong>

- 常数因子可以省略：`5n = O(n)`
- 只有最高阶项起作用：`3n² + 10n + 7 = O(n²)`
- 对数的底无关紧要：`log₂ n = O(log n)`

<span class="halvany">相关记号：Ω（下界）、Θ（精确阶）。</span>

---

<!-- _class: kicsi -->

## 常见的增长阶

| 记号 | 名称 | 例子 |
|---|---|---|
| O(1) | 常数阶 | 按下标访问数组元素、栈的 `push` |
| O(log n) | 对数阶 | 二分查找 |
| O(n) | 线性阶 | 顺序查找、求和、求最大值 |
| O(n log n) | “n log n”阶 | 归并排序、快速排序（平均） |
| O(n²) | 平方阶 | 冒泡排序、考察所有元素对 |
| O(2ⁿ) | 指数阶 | 考察所有子集 |

<div class="doboz tipp">

经验法则：当 n = 10⁶ 时，O(n log n) 完全可以接受，O(n²) 则不行。

</div>

---

## 从代码确定阶

<div class="ket-hasab">
<div>

```java
// O(n)
for (int i = 0; i < n; i++)
    sum += a[i];

// O(n²)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        count++;
```

</div>
<div>

```java
// O(log n) – 每次减半
while (n > 1)
    n = n / 2;

// O(n) + O(n²) = O(n²)
for (int i = 0; i < n; i++) ...
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) ...
```

</div>
</div>

- <strong>顺序执行：</strong>代价相加 → 取较大者
- <strong>嵌套：</strong>代价相乘
- <strong>减半：</strong>如果每一步都把问题规模减半 → log n

---

## 空间复杂度

不仅时间，<strong>内存</strong>也是一种资源。

- <strong>空间复杂度：</strong>除输入之外所需的内存，表示为 n 的函数
- 顺序查找和二分查找：<strong>O(1)</strong> – 只需几个辅助变量
- 复制一个数组：<strong>O(n)</strong>

<div class="doboz">

我们常常需要<strong>在时间和空间之间权衡</strong>：多用一些内存（例如哈希表，第 11 周），查找就可以更快。

</div>

---

<!-- _class: fejezet -->

# 在数组中查找

---

## 顺序（线性）查找

![w:900](kepek/h02_linearis.svg)

- 从前往后，把每个元素与要找的值比较
- 数组<strong>不需要</strong>有序
- 在链表上同样适用（顺序访问）

---

<!-- _class: kicsi -->

## 顺序查找 – 算法

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function LinearSearch(A, n, x)
  i ← 1
  While i ≤ n and A[i] ≠ x
    i ← i + 1
  End while
  If i ≤ n then
    Return i
  else
    Return 0       // 未找到
  End if
End function
```

<strong>步数：</strong>最坏情况 <strong>O(n)</strong>

</div>
<div>

<span class="cimke java">Java</span>

```java
static int linearSearch(int[] a, int x) {
    int i = 0;
    while (i < a.length && a[i] != x)
        i++;
    return i < a.length ? i : -1;
}
```

<span class="cimke go">Go</span>

```go
func linearSearch(a []int, x int) int {
    for i, v := range a {
        if v == x {
            return i
        }
    }
    return -1
}
```

</div>
</div>

---

## 注意：条件的顺序！

```text
While i ≤ n and A[i] ≠ x
```

- 当 `i = n + 1` 时，`A[i]` 是一个<strong>不存在</strong>的元素
- 得益于<strong>短路求值</strong>，这仍然是正确的：如果 `i ≤ n` 为假，就不会计算 `A[i] ≠ x`

<div class="doboz figyelem">

如果顺序反过来（`A[i] ≠ x and i ≤ n`），Java 会抛出 `ArrayIndexOutOfBoundsException`,Go 会报 `index out of range` 错误。

</div>

---

<!-- _class: kicsi -->

## 哨兵查找

<strong>思路：</strong>把要找的值放在数组末尾（第 <em>n</em> + 1 个位置） – 这样一定能找到，也就不必检查下标边界。

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function SentinelSearch(A, n, x)
  A[n + 1] ← x          // 哨兵
  i ← 1
  While A[i] ≠ x
    i ← i + 1
  End while
  If i ≤ n then Return i
  else Return 0
End function
```

</div>
<div>

- 每一步<strong>一次</strong>比较，而不是两次
- 仍然是 <strong>O(n)</strong>，但比较次数约减少一半
- 数组末尾需要一个<strong>额外的位置</strong>

| 方法 | x = 4 不存在，n = 7 |
|---|---|
| 普通 | 15 次比较 |
| 哨兵 | 8 次比较 |

</div>
</div>

<span class="halvany">第 10 周的带哨兵链表会再次用到哨兵的思想。</span>

---

## 在有序数组中顺序查找

如果数组<strong>有序</strong>，一旦遇到<strong>大于</strong> `x` 的元素就可以停止。

```text
Function SortedLinear(A, n, x)
  i ← 1
  While i ≤ n and A[i] < x
    i ← i + 1
  End while
  If i ≤ n and A[i] = x then Return i
  else Return 0
End function
```

- 查找失败时平均更快
- 但最坏情况仍然是 <strong>O(n)</strong> – 能不能更好？

---

## 二分查找 – 思路

<strong>前提：</strong>数组<strong>有序</strong>。

1. 看<strong>中间</strong>的元素
2. 如果正是要找的：完成
3. 如果要找的值<strong>更小</strong>：在左半部分继续
4. 如果要找的值<strong>更大</strong>：在右半部分继续

每一步查找范围都<strong>减半</strong>。

<div class="doboz tipp">

就像在字典里查一个词（或在电话簿里查一个名字）：我们不会一页一页地翻，而是从中间翻开，再决定往哪边走。

</div>

---

## 二分查找 – 示例

![w:1100](kepek/h02_binaris.svg)

---

<!-- _class: kicsi tomor -->

## 二分查找 – 算法

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function BinarySearch(A, n, x)
  lo ← 1
  hi ← n
  While lo ≤ hi
    k ← (lo + hi) div 2
    If A[k] = x then
      Return k
    else if A[k] < x then
      lo ← k + 1
    else
      hi ← k − 1
    End if
  End while
  Return 0
End function
```

</div>
<div>

<span class="cimke java">Java</span>

```java
static int binarySearch(int[] a, int x) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
```

<span class="cimke go">Go</span>

```go
for lo <= hi {
    mid := lo + (hi-lo)/2
    switch {
    case a[mid] == x: return mid
    case a[mid] < x:  lo = mid + 1
    default:          hi = mid - 1
    }
}
```

</div>
</div>

---

## 二分查找 – 效率

每一步之后，范围的大小至多为原来的一半：n → n/2 → n/4 → … → 1

至多 <strong>⌊log₂ n⌋ + 1</strong> 步 → <strong>O(log n)</strong>

| n | 顺序查找（最坏） | 二分查找（最坏） |
|---|---|---|
| 10 | 10 | 4 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
| 1 000 000 000 | 1 000 000 000 | 30 |

<div class="doboz">

在全中国人口（14 亿）的有序名单中找一个名字：<strong>至多 31 步</strong>。

</div>

---

## 二分查找 – 常见错误

- 数组<strong>无序</strong> → 结果错误（而且没有错误提示！）
- 用 `lo < hi` 代替 `lo ≤ hi` → 漏掉只有一个元素的范围
- 用 `lo ← k` 代替 `lo ← k + 1` → 可能<strong>死循环</strong>
- `(lo + hi) / 2` → 下标很大时<strong>溢出</strong>
  应改为：`lo + (hi − lo) / 2`

<div class="doboz tipp">

Java 类库的 `Arrays.binarySearch` 函数中这个错误存在了很多年（2006 年才修复）。

</div>

<strong>内置版本：</strong>Java `Arrays.binarySearch(a, x)` · Go `sort.SearchInts(a, x)`

---

## 顺序查找还是二分查找？

| | 顺序 | 二分 |
|---|---|---|
| 前提 | 无 | <strong>有序</strong>数组 |
| 访问 | 顺序访问即可 | 需要<strong>直接</strong>访问 |
| 步数 | O(n) | O(log n) |
| 在链表上 | ✓ | ✗（无法直接访问） |

<div class="doboz">

如果要在同一组数据上多次查找，值得<strong>先排序一次</strong>（O(n log n)，第 13 周）；之后每次查找都是 O(log n)。

</div>

---

## 小结

- 效率用<strong>步数随输入规模的增长</strong>来衡量
- 通常考察<strong>最坏情况</strong>
- <strong>大O：</strong>省略常数和低阶项
- 阶的大小：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
- <strong>顺序查找：</strong>O(n)，适用于任何数组 · 用哨兵可减少比较次数
- <strong>二分查找：</strong>O(log n)，只适用于可直接访问的<strong>有序</strong>数组

<strong>下周：</strong>数组 – 一维和多维数组、存储方式、地址计算、动态数组。

---

## 复习题

1. `3n² + 100n + 5` 的阶（大O）是什么？`n + log n` 呢？
2. 判断对错：二分查找是 O(n) 的。
3. 判断对错：二分查找在链表上也是 O(log n) 步。
4. 在 500 个元素的数组中，二分查找至多需要多少步？
5. 在无序数组上进行二分查找会怎样？
6. 下面代码的阶是什么？
   `for (i = 1; i < n; i = i * 2) for (j = 0; j < n; j++) …`

<!--
答案：1. O(n²);O(n)  2. 错（O(log n)）  3. 错 – 无法直接访问，连到达中间元素都要 O(n)
4. ⌊log2 500⌋ + 1 = 8 + 1 = 9  5. 可能给出错误（无意义）的结果：可能漏掉实际存在的元素；没有错误提示。
6. 外层循环执行 log n 次，内层 n 次 → O(n log n)
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# 实践课

---

<!-- _class: gyak -->

## 示例程序

| 程序 | Java | Go | 演示内容 |
|---|---|---|---|
| 顺序查找 | `LinearSearch.java` | `w02/linearsearch` | 普通、哨兵和有序三种写法；比较次数 |
| 二分查找 | `BinarySearch.java` | `w02/binarysearch` | 打印每一步，最坏情况表 |
| 计时 | `Timing.java` | `w02/timing` | O(n)、O(log n)、O(n²) 的实际表现 |

<div class="doboz tipp">

运行 `Timing` 程序并观察：n 增大 10 倍时，顺序查找和二分查找的时间怎样变化？n 加倍时，O(n²) 算法的时间怎样变化？

</div>

---

<!-- _class: gyak -->

## 练习

1. <strong>最大值：</strong>返回数组中最大元素的下标！需要多少步？
2. <strong>计数：</strong>数组中有多少个元素等于 `x`？
3. <strong>第一次出现：</strong>在有序数组中某个值可能出现<strong>多次</strong>，用 O(log n) 步找到 `x` <strong>第一次</strong>出现的位置！（`[1,2,2,2,5] , x=2 → 1`）
4. <strong>插入位置：</strong>返回 `x` 可以插入的下标，使数组仍然有序！
5. <strong>整数平方根：</strong>用二分查找求满足 *r*² ≤ <em>n</em> 的最大 <em>r</em>!
6. <strong>猜数字：</strong>计算机想一个 1 到 1000 之间的数，我们得到“小了/大了”的回答。至多需要问几次？

参考答案：`Exercises02.java`、`w02/exercises`

---

<!-- _class: gyak -->

## 课后作业

1. 写出阶（大O）！
   a) `for i ← 1 to n: for j ← 1 to 10: …`
   b) `for i ← 1 to n: for j ← 1 to i: …`
   c) `i ← n; While i > 0: i ← i div 3`
2. 在纸上对数组 `[3, 8, 15, 21, 30, 42, 57, 66, 81]` 分别查找 `x = 57` 和 `x = 10`!写出每一步的 `lo`、`hi` 和 `k`！
3. 编写函数，用 O(log n) 步统计 `x` 在<strong>有序</strong>数组中出现的次数！

<!--
答案：1a) O(n)  1b) n(n+1)/2 → O(n²)  1c) O(log n)
2. x=57:(1,9,k=5:30<57) → (6,9,k=7:57) 找到,下标 7。  x=10:(1,9,5:30>10) → (1,4,2:8<10) → (3,4,3:15>10) → (3,2) 结束，返回 0。
3. 最后一次出现的位置 − 第一次出现的位置 + 1（两次二分查找）。
-->