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.
搜索算法
｜
93
搜索算法
表
5
-
1
：顺序搜索的性能
n
/ 个
p
=
1
.
0
p
=
0
.
5
p
=
0
.
25
p
=
0
.
0
4,096 0.0057s 0.0087s 0.0101s 0.0116s
8,192 0.0114s 0.0173s 0.0202s 0.0232s
16,384 0.0229s 0.0347s 0.0405s 0.0464s
32,768 0.0462s 0.0697s 0.0812s 0.0926s
65,536 0.0927s 0.1391s 0.1620s 0.1853s
131,072 0.1860s 0.2786s 0.3245s 0.3705s
5.2 二分搜索
二分搜索
在有序的集合上可以表现出比
顺序查找
更好的性能。它每次将待查询的集合规
模折半，直至找到目标元素，或者发现目标元素不在当前的集合中。
5.2.1 输入 / 输出
二分搜索
的输入是一个有序集合
A
，集合中的每个元素可以通过一个索引值（对于数组
来说就是下标）来访问。所谓一个集合有序，就是给定两个索引值
i
和
j
，当且仅当
i
<
j
时，
A
[
i
] <
A
[
j
]
。假设已经创建了一个数据结构来保存这些元素（或者这些元素的指针）
，
并且能够维护索引值的顺序。
二分搜索
的输出只是
true
或者
false
。
5.2.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,
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.