April 2020
Intermediate to advanced
210 pages
4h 47m
Chinese
Content preview from 数据压缩入门
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.
14
｜
第
2
章
2.2.1
二分查找
假定有一个已经确定了范围且排好序的整数数组，比如说
0~15
，我们想找出数值
10
在这
个数组中的位置。
二分查找
算法的工作原理是这样的：首先将数组中的数据集分成两半，然后判断要找的数
值
10
比处于中间位置的枢轴值是大还是小
3
。根据对比的结果，我们将数组分成了两半，并
保留包含
10
的那一半数据进行进一步的查找。然后再次将
10
与新的枢轴值进行比较，并
继续将数组分成两半。一直这样进行下去，直到最终只剩下我们要找的数值
10
。（如果这
听上去与前面所说的
20
个问题
游戏有些相似，那是因为事实确实如此！）
在查找的过程中，每当我们比较枢轴值与要查找的值的大小时，不妨输出一个二进制位来
表示我们所做的决定（约定用
0
表示小于，用
1
表示大于）。
实际操作更便于理解，下面就实际操作一遍，具体如图
2-1
所示。
查找数值10
大于 -> 1
小于 -> 0
小于 -> 0
大于 -> 1
输出 = 1010
正好是数值10
的二进制表示
图 2-1：在一个有限的数值范围内进行二分查找。如果将每一步所做的决定（选择大值端还是小值端）
都保存下来，最终就会得到要查找的数值的二进制形式
注
3
：
当然，如果一个数组包含偶数个元素，那么真正处于中间的元素是不存在的。这种情况下，可以根据
喜好从中间偏左或中间偏右这两个元素中任选一个。
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.