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.
96
｜
第
5
章
表
5-3
列出了在磁盘上执行
524 288
次查找的时间。为了简单起见，目标元素要么肯定
存在（例如
p
= 1.0
）
，要么肯定不存在（例如，在集合
[0,
n
]
中查找
-1]
。数据文件只是
简单地存储了升序排列的整数，每个整数是
4
个字节。磁盘存储的劣势是非常明显的，
因为相比，表
5-3
的结果要比表
5-2
大很多，所用时间约为表
5-2
中的
400
倍。而且当
数据规模加时，搜索需要的时间只是增加了一个固定值，这种特性非常明显地表明二分
搜索是
O(log
n
)
的算法。
表
5
-
3
：在二级存储器上执行
524
288
次查找的二分搜索的性能
n
/
个
p
= 1.0
p
= 0.0
4,096 1.2286s 1.2954s
8,192 1.3287s 1.4015s
16,384 1.4417s 1.5080s
32,768 6.7070s 1.6170s
65,536 13.2027s 12.0399s
131,072 19.2609s 17.2848s
262,144 24.9942s 22.7568s
524,288 30.3821s 28.0204s
5.2.5 衍生算法
当二分搜索支持“搜索
/
插入”操作时，所有数组下标均为非负数。例
5-4
的
Python
给
出了一个名为
bs_contains
的方法，如果搜索的目标元素不在有序数组中，那么它会返
回一个负值
p
。
-(
p
+ 1)
便是这个
目标元素
应该被插入的位置。由于数据结构是数组，我
们需要移动这个位置后面的所有元素。
例
5-4
：
Python
的搜索插入实现
def ...
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.