企业官网建设流程全解析

上一课我们学了冒泡、选择、插入，知道它们大多是O(n²)；
本课就要回答一个非常重要的问题：

“有没有更快的排序和查找方法？”

第十一课 高效排序与二分查找

——为什么“每次砍掉一半”会这么快？

一、本课的学习目标

对于CSP-J 初赛复习，更重要的是做到：

第一层：认识

知道：

冒泡排序 O(n²) 选择排序 O(n²) 插入排序 O(n²) 快速排序 O(n log n) 归并排序 O(n log n) 堆排序 O(n log n) 二分查找 O(log n)

第二层：理解

知道：

为什么二分查找这么快？

以及：

为什么快速排序、归并排序可以达到O(n log n)？

第三层：程序阅读

熟练掌握二分查找代码：

mid = (l+r)/2;

并可以判断：

答案在左边 还是右边

并熟练掌握：

快速排序、归并排序 程序模版

这是初赛常见的考点。

二、先复习上一课：冒泡排序为什么慢？

假设有：

100万个数字

如果使用冒泡排序：

O(n²)

那么工作量大约是：

n²

也就是：

1,000,000² = 1,000,000,000,000

一万亿级别。

这就很可怕了。

三、所以我们需要“聪明”的算法

上一课的排序思路基本是：

一个一个比较。

而这一课开始，我们学习一种非常重要的算法思想：

分而治之

也就是：

不要一次处理一个巨大的问题，而是把大问题变成几个小问题。

这也是快速排序、归并排序背后的重要思想。

四、二分查找

先不讲排序。

我们先来看一个生活中的问题。

老师有一本：

按学号排列的学生名单。

现在要找：

学号 537

如果从第一个开始找：

1 2 3 4 5 …… 537

这是：

顺序查找

最坏需要检查：

n

个数据。

所以：

O(n)

讲义也明确将顺序查找列为O(n)。

五、如果名单已经排好序呢？

假设：

1 2 3 4 5 ... 1000

我要找：

537

为什么一定要从1开始？

完全没必要！

我们直接看中间：

500

发现：

537 > 500

那么：

1 ~ 499

全部不用看了！

只需要看：

501 ~ 1000

一次就砍掉了一半。

六、再砍一半

现在范围：

501 ~ 1000

中间大约：

750

因为：

537 < 750

所以：

751 ~ 1000

又全部不用看。

现在只剩：

501 ~ 749

七、继续砍

每一次：

剩余范围 ↓ 砍掉一半

例如：

1000 ↓ 500 ↓ 250 ↓ 125 ↓ 62 ↓ 31 ↓ 16 ↓ 8 ↓ 4 ↓ 2 ↓ 1

很快就能找到。

所以：

二分查找的核心思想

每次比较中间元素，然后把不可能的一半直接扔掉。

八、为什么叫“二分”？

因为：

二 + 分

就是：

把问题分成两部分。

每次只保留其中一部分。

所以：

n ↓ n/2 ↓ n/4 ↓ n/8 ↓ …… ↓ 1

九、二分查找为什么是 O(log n)？

这是第10课和第12课的重要连接。

假设：

n = 1024

每次除以2：

1024 512 256 128 64 32 16 8 4 2 1

需要：

10次

因为：

2¹⁰ = 1024

所以：

log₂1024 = 10

因此：

二分查找 O(log₂n)

我们要特别强调：

二分查找要求数列有序。

十、为什么二分查找必须有序？

这是初赛经常考的知识点。

假设：

8 2 10 3 7 1 9

我要找：

7

我看中间：

3

发现：

7 > 3

能不能说：

“那我去右边找？”

不能。

因为右边：

7 1 9

左边：

8 2 10

两边都可能有7。

所以：

无序数据不能直接使用普通二分查找。

十一、有序为什么就可以？

例如：

1 2 3 4 5 6 7 8 9 10

如果中间是：

5

我要找：

8

因为：

8 > 5

所以左边：

1 2 3 4

全部不可能。

这就是：

“有序”给了我们排除答案的依据。

十二、二分查找最简单的代码

先给同学们，写一个经典版本：

int l = 0; int r = n - 1; while(l <= r) { int mid = (l + r) / 2; if(a[mid] == x) { cout << "找到了"; break; } else if(a[mid] < x) { l = mid + 1; } else { r = mid - 1; } }

这一段代码同学们要理解掌握。

十三、先看三个变量

int l = 0; int r = n - 1;

它们表示：

l = 当前查找范围的左边界 r = 当前查找范围的右边界

例如：

1 2 3 4 5 6 7 8 9

如果：

l=0 r=8

那么搜索：

[0,8]

十四、mid是什么？

int mid=(l+r)/2;

意思：

取当前区间的中间位置。

例如：

l=0 r=8

那么：

mid=(0+8)/2 =4

所以：

a[4]

就是中间元素。

十五、如果a[mid] == x

直接：

if(a[mid] == x)

说明：

找到了！

十六、如果a[mid] < x

例如：

a[mid] = 50 x = 80

因为数组是升序：

左边 ≤ 50

所以80不可能在左边。

因此：

l = mid + 1;

把左边扔掉。

十七、如果a[mid] > x

例如：

a[mid] = 80 x = 50

因为数组是升序：

右边 ≥ 80

所以50不可能在右边。

因此：

r = mid - 1;

把右边扔掉。

十八、给大家一个非常简单的口诀

二分查找一定要记住：

中间小，去右边；中间大，去左边；相等就找到了。

也就是：

a[mid] < x → l = mid + 1 a[mid] > x → r = mid - 1 a[mid] == x → 找到

十九、模拟题

数组：

1 3 5 7 9 11 13 15 17

寻找：

13

下标：

0 1 2 3 4 5 6 7 8

第一次：

l=0 r=8 mid=4

所以：

a[4]=9

因为：

9 < 13

所以：

l=5

第二次：

l=5 r=8 mid=6

a[6]=13

找到！

只用了：

2次。

二十、如果用顺序查找呢？

数组：

1 3 5 7 9 11 13

寻找13：

1 3 5 7 9 11 13

需要：

7次

而二分：

9 13

只需要：

2次

这就是算法之间的巨大差别。

二十一、二分查找最大的价值

它告诉大家一个非常重要的算法思想：

不要总是“一个一个试”。

而要问：

能不能一次排除掉大量不可能的情况？

这是以后学习：

• 二分答案

• 搜索

• 贪心

• 动态规划

时都非常重要的思想。

二十二、接下来进入快速排序

二分查找解决的是：

快速寻找一个元素。

那么问题来了：

能不能也把排序做得更快？

可以。

一个非常经典的算法就是：

快速排序

讲义将快速排序列为O(n log n)的较快排序算法。

二十三、快速排序的核心思想

假设：

8 3 6 2 5 1 7 4

我们先选择一个数字作为：

基准值 pivot

比如：

pivot = 5

然后把数字分成两边：

比5小 比5大 2 3 1 4 8 6 7

于是：

2 3 1 4 | 5 | 8 6 7

现在我们发现：

原来的8个数字的大问题，被拆成了两个小问题。

二十四、然后怎么办？

对左边继续排序：

2 3 1 4

对右边继续排序：

8 6 7

这就是：

递归 + 分治。

所以快速排序和第7课：

递归

又联系起来了。

二十五、快速排序的思想图

可以画成：

8 3 6 2 5 1 7 4 │ pivot=5 / \ ↓ ↓ 2 3 1 4 8 6 7 │ │ 继续分 继续分 ↓ ↓ …… ……

直到每一部分非常小。

二十六、为什么快速排序可能是 O(n log n)？

只要理解：

如果每一次都能比较均匀地分成两部分：

n ↓ n/2 + n/2 ↓ n/4 + n/4 + n/4 + n/4 ↓ ……

大约需要：

log n

层。

而每一层处理的数据总量大约是：

n

所以：

n × log n

得到：

O(n log n)

讲义将快速排序列为这一复杂度级别。

二十七、但是快速排序有一个问题

如果pivot选得非常糟糕呢？

例如：

1 2 3 4 5 6 7 8

每次都选择：

1

那么可能变成：

1 | 2 3 4 5 6 7 8

然后：

1 | 2 | 3 4 5 6 7 8

不断只分出一个元素。

这样就没有做到真正的“二分”。

所以：

快速排序的O(n log n)是通常/理想划分情况下的复杂度描述；

最坏情况复杂度会退化到O(n²)。

二十八、归并排序

第二个重要的高效排序：

归并排序。

它的思想非常漂亮：

先分，再排，再合。

二十九、例如：

8 3 6 2 5 1 7 4

先分：

8 3 6 2 | 5 1 7 4

继续分：

8 3 | 6 2 | 5 1 | 7 4

继续：

8 | 3 | 6 | 2 | 5 | 1 | 7 | 4

现在每一组只有一个元素。

一个元素：

天然有序。

三十、然后开始“合并”

例如：

8 3

合并：

3 8

再：

6 2

合并：

2 6

于是：

3 8 2 6

继续合并：

2 3 6 8

右边：

1 5 4 7

最终：

1 2 3 4 5 6 7 8

三十一、归并排序最重要的两个动作

分 ↓ 合

所以叫：

归并排序

“归并”就是：

把几个已经有序的小部分合并成一个更大的有序部分。

三十二、快速排序和归并排序有什么区别？

可以用一句话记：

快速排序

选一个基准，把数据分到两边。

归并排序

先不断拆开，最后把有序部分合起来。

三十三、两种算法都使用了什么思想？

都是：

分治

即：

大问题 ↓ 小问题 ↓ 分别解决 ↓ 组合结果

三十四、堆排序

快速排序 堆排序 归并排序

都属于：

O(n log n)

但是对于CSP-J初赛复习：

大纲要求，只了解堆排序概念，不深入实现。

三十五、速度排行榜

三十六、时间复杂度的比较

假设：

n = 1,000,000

那么：

O(n)

大约：

1,000,000

O(log n)

大约：

20

因为：

2²⁰ ≈ 1,000,000

这就非常夸张了：

顺序查找： 约100万次 二分查找： 约20次

同学们此时应该理解：

算法不是“小优化”，而可能是数量级的差别。

三十七、CSP-J经常考的陷阱

陷阱1：看到“二分”就认为一定是O(log n)

不够严谨。

必须满足：

能够有效地每次排除掉一半。

标准二分查找还要求：

数列有序。

我们明确要强调这一点。

陷阱2：不排序就二分

例如：

int a[5]={5,2,4,1,3};

不能直接二分。

应该先：

sort(a,a+5);

变成：

1 2 3 4 5

然后才能进行普通二分查找。

所以经常出现：

排序 + 二分查找

这样的组合。

三十九、一个综合例题

int a[8]={8,3,6,2,5,1,7,4}; sort(a,a+8); int x=7; int l=0,r=7; while(l<=r) { int mid=(l+r)/2; if(a[mid]==x) { cout<<mid; break; } else if(a[mid]<x) l=mid+1; else r=mid-1; }

问：

最后输出什么？

第一步：排序

原数组：

8 3 6 2 5 1 7 4

排序：

1 2 3 4 5 6 7 8

下标：

0 1 2 3 4 5 6 7

第二步：二分

第一次：

l=0 r=7 mid=3

a[3]=4

因为：

4 < 7

所以：

l=4

第二次：

l=4 r=7 mid=5

a[5]=6

因为：

6 < 7

所以：

l=6

第三次：

l=6 r=7 mid=6

a[6]=7

找到。

输出：

6

四十、就把前面的知识串起来：

数组 ↓ sort ↓ 排序 ↓ 下标 ↓ while ↓ 二分 ↓ l/r/mid ↓ 条件判断

这正是CSP-J初赛程序阅读题的典型风格：

不是单独考某一个知识点，而是把多个基础知识拼在一起。

四十一、二分查找还有一个重要问题：边界

这一部分要易错点。

例如：

while(l<=r)

什么时候停止？

当：

l > r

说明：

查找区间已经空了。

所以没有找到。

四十二、为什么是mid+1？

如果：

a[mid] < x

说明：

mid

这个位置已经确定不是答案。

所以：

l=mid+1;

不能写：

l=mid;

否则可能一直卡在同一个位置。

四十三、为什么是r=mid-1？

同样：

a[mid] > x

说明：

mid

不是答案。

所以：

r=mid-1;

而不是：

r=mid;

四十四、给大家一个“边界口诀”

排除mid，就要跨过mid。

所以：

去右边： l = mid + 1 去左边： r = mid - 1

这一句话以后做二分题会非常有用。

四十五、本课重要的思想

前面讲：

复杂度。

上节课讲：

基础排序。

本课真正要同学们学会的是：

“减少问题规模”。

例如：

顺序查找

n → n-1 → n-2 → n-3 → ...

一次只减少一点。

二分查找

n → n/2 → n/4 → n/8 → ...

每次砍掉一半。

所以：

O(n)

和：

O(log n)

差距巨大。

四十六、分治思想

快速排序：

一个大问题 ↓ 分成两个小问题 ↓ 再继续分 ↓ 越来越小

归并排序：

一个大问题 ↓ 不断拆小 ↓ 小问题解决 ↓ 不断合并

所以本课实际上是在给大家埋下一颗非常重要的种子：

分治思想。

四十七、本课知识地图

高效算法 │ ┌───────────┴───────────┐ ↓ ↓ 查找 排序 │ │ ┌────┴────┐ ┌──────┼──────┐ ↓ ↓ ↓ ↓ ↓ 顺序查找 二分查找 快排 归并 堆排 │ │ │ │ │ O(n) O(log n) O(nlogn) O(nlogn) │ ↓ 必须有序 │ ↓ 每次排除一半

四十八、本课CSP-J必背清单

① 顺序查找

O(n)

一个一个找。

② 二分查找

O(log n)

核心：

每次排除一半。

条件：

数列有序。

③ 冒泡、选择、插入

O(n²)

④ 快速排序

O(n log n)

核心：

分治 + 基准值划分。

⑤ 归并排序

O(n log n)

核心：

先分，再合并。

⑥ 堆排序

O(n log n)

本课只要求了解。

四十九、课后练习（二分）

练习1

判断下面哪些数组可以直接使用二分查找：

① 1 2 3 4 5 ② 5 3 8 1 2 ③ 10 20 30 40 ④ 9 7 5 3 1

注意：

降序数组也可以设计相应的二分查找，但代码中的判断方向必须跟着改变。

练习2

手算：

int a[]={1,3,5,7,9,11,13,15,17};

寻找：

13

要求写出每一次：

l r mid a[mid]

练习3

判断复杂度：

for(int i=1;i<n;i*=2)

答案：

O(log n)

五十、课后练习（高效排序）

同学们来书写：

快速排序

选pivot ↓ 分左右 ↓ 递归

归并排序

不断拆分 ↓ 单个元素 ↓ 有序合并

要讲解给其他同学，自己为何这样写。

五十一、讲一个小故事

老师给两个同学同一道题：

从100万个已经排好序的数字里找一个数字。

小明：

1个 2个 3个 4个 ……

一个一个找。

小华：

先看中间 ↓ 砍掉一半 ↓ 再看中间 ↓ 再砍一半 ↓ ……

“你们两个，谁的方法更好一些？”

我们重要的不是比谁更聪明。

而是：

谁找到了更好的方法。

我们的算法竞赛真正训练的，不只是：

“你会不会写代码？”

而是：

面对一个很大的问题，你能不能找到一种方法，让计算机少做很多很多没有必要的事情。

这就是为什么我们要学习：

O(n) ↓ O(log n) O(n²) ↓ O(n log n)

优秀的算法，不只是能把问题解决，还要更快，更好的做出来。