August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
搜索算法
｜
95
搜索算法
在上述代码中，使用了三个变量：
low
、
high
和
mid
。
low
是当前数组范围的最小下标，
high
是最大下标，
mid
则是当前数组范围的中点。这段代码的性能取决于
while
循环执
行的次数。
二分搜索
虽然在实现上稍稍复杂了些，却能获得巨大的性能提升。但是，当数据无法存
储在简单的内存数据结构（例如数组）中时，实现会变得更加复杂。当集合较大时，我
们可以将其以某种形式存储在二级存储器中，例如磁盘上的文件。在这种情况下，对于
第
i
个元素，能够根据它在文件中的偏移量来访问。如果使用的是二级存储器，那么查
找一个元素的费用主要在访问二级存储器上。因此，这时可能需要考虑其他类似于
二分
搜索
的算法。
5.2.4 算法分析
二分搜索
每次执行循环时都会将问题规模大致减半。将大小为
n
的集合折半的最大次数为
1+
⎣
log(
n
)
⎦
。如果只需要一个操作就能决定两个元素是否相等、小于或者大于，那么
总的比较次数为
1+
⎣
log(
n
)
⎦
，从而可以推出算法的性能是
O
(log
n
)
。
和前面相同，我们运行了
100
次实验，每次实验将会对存储在内存中、大小为
n
（
n
的范
围是
4096~524 288
）的数据执行
524 288
次查找，目标元素存在的概率是
p
（在
1.0
、
0.5
和
0.0
处采样）。表
5-2
列出了抛弃最好和最坏的实验结果后剩余实验的平均结果。
表
5
-
2
：在内存中执行
524
288
次查找，二分搜索和顺序查找的比较
n
/ 个 顺序搜索 二分搜索
p
= 1.0
p
= 0.5
p
= 0.0
p
= 1.0
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.