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.
搜索算法
｜
97
搜索算法
"""
如果不存在，即插入合适的位置
"""
idx = bs_contains(ordered, target)
if idx < 0:
ordered.insert(-(idx + 1), target)
从一个有序数组中插入或者删除元素是非常困难的，而且随着数组规模的增加，这些操
作将会更加低效，因为每个数组条目必须包含一个有效的元素。所以，插入操作需要扩
展整个数组，并且平均需要移动一半的元素；删除操作需要缩短数组，并且也需要移动
一半的元素。
5.3 散列搜索
前面讨论的搜索算法都有一些限制条件，例如小数据量（
顺序查找
）或者数据集合必须
有序（
二分搜索
）。我们需要更强大的算法来破除这些限制条件，例如能够处理更大的
数据规模或者无序的数据，抑或二者兼有。最常用的一种方法是使用
散列函数
来将目标
元素的一个或者多个特征转换成一个值，用这个值来索引散列表中的某个位置。在平均
情况下，
散列搜索
的性能要比本章描述的其他算法更好。许多算法书籍是在讨论
散列表
时才介绍
散列搜索
（
Cormen et al., 2009
），读者也可以在数据结构书籍中的相关章节找
到它。
散列搜索
将集合
C
的所有
n
个元素首先加载到一个有着
b
个桶的散列表
H
中。该
预处理
需要差不多
O
(
n
)
的时间，虽然时间看起来不少，但将改善未来搜索的性能。这就是
散列
函数
的威力。
散列函数
是一个确定型函数，它将每个元素
C
i
映射成一个整数值
h
i
，这里暂时假定
0
≤
h
i
<
b
。在插入数据的过程中，元素
C
i
会被插入桶
H
[
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.