-
Notifications
You must be signed in to change notification settings - Fork 25
/
ch11s06.html
122 lines (110 loc) · 15 KB
/
ch11s06.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>6. 折半查找</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch11.html" title="第 11 章 排序与查找" /><link rel="prev" href="ch11s05.html" title="5. 线性查找" /><link rel="next" href="ch12.html" title="第 12 章 栈与队列" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">6. 折半查找</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11s05.html">上一页</a> </td><th width="60%" align="center">第 11 章 排序与查找</th><td width="20%" align="right"> <a accesskey="n" href="ch12.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2746698"></a>6. 折半查找</h2></div></div></div><p>如果不是从一组随机的序列里查找，而是从一组排好序的序列里找出某个元素的位置，则可以有更快的算法：</p><div class="example"><a id="id2746710"></a><p class="title"><b>例 11.4. 折半查找</b></p><div class="example-contents"><pre class="programlisting">#include <stdio.h>
#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
while (start <= end) {
mid = (start + end) / 2;
if (a[mid] < number)
start = mid + 1;
else if (a[mid] > number)
end = mid - 1;
else
return mid;
}
return -1;
}
int main(void)
{
printf("%d\n", binarysearch(5));
return 0;
}</pre></div></div><br class="example-break" /><p>由于这个序列已经从小到大排好序了，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“<span class="quote">如果待查找的元素存在，一定位于序列的后半部分</span>”，这样可以把搜索范围缩小到后半部分，然后再次使用这种算法迭代。这种“<span class="quote">每次将搜索范围缩小一半</span>”的思想称为折半查找（Binary Search）<a id="id2746741" class="indexterm"></a>。思考一下，这个算法的时间复杂度是多少？</p><p>这个算法的思想很简单，不是吗？可是<a class="xref" href="bi01.html#bibli.pearls" title="Programming Pearls">[<abbr class="abbrev">编程珠玑</abbr>]</a>上说作者在课堂上讲完这个算法的思想然后让学生写程序，有90%的人写出的程序中有各种各样的Bug，读者不信的话可以不看书自己写一遍试试。这个算法容易出错的地方很多，比如<code class="literal">mid = (start + end) / 2;</code>这一句，在数学概念上其实是<code class="literal">mid = ⌊(start + end) / 2⌋</code>，还有<code class="literal">start = mid + 1;</code>和<code class="literal">end = mid - 1;</code>，如果前者写成了<code class="literal">start = mid;</code>或后者写成了<code class="literal">end = mid;</code>那么很可能会导致死循环（想一想什么情况下会死循环）。</p><p>怎样才能保证程序的正确性呢？在<a class="xref" href="ch11s02.html#sortsearch.insertion">第 2 节 “插入排序”</a>我们讲过借助Loop Invariant证明循环的正确性，<code class="literal">binarysearch</code>这个函数的主体也是一个循环，它的Loop Invariant可以这样描述：<span class="emphasis"><em>待查找的元素<code class="literal">number</code>如果存在于数组<code class="literal">a</code>之中，那么一定存在于a[start..end]这个范围之间，换句话说，在这个范围之外的数组<code class="literal">a</code>的元素中一定不存在<code class="literal">number</code>这个元素</em></span>。以下为了书写方便，我们把这句话表示成<code class="literal">mustbe(start, end, number)</code>。可以一边看算法一边做推理：</p><pre class="programlisting">int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
/* 假定a是排好序的 */
/* mustbe(start, end, number)，因为a[start..end]就是整个数组a[0..LEN-1] */
while (start <= end) {
/* mustbe(start, end, number)，因为一开始进入循环时是正确的，每次循环也都维护了这个条件 */
mid = (start + end) / 2;
if (a[mid] < number)
/* 既然a是排好序的，a[start..mid]应该都比number小，所以mustbe(mid+1, end, number) */
start = mid + 1;
/* 维护了mustbe(start, end, number) */
else if (a[mid] > number)
/* 既然a是排好序的，a[mid..end]应该都比number大，所以mustbe(start, mid-1, number) */
end = mid - 1;
/* 维护了mustbe(start, end, number) */
else
/* a[mid] == number，说明找到了 */
return mid;
}
/*
* mustbe(start, end, number)一直被循环维护着，到这里应该仍然成立，在a[start..end]范围之外一定不存在number，
* 但现在a[start..end]是空序列，在这个范围之外的正是整个数组a，因此整个数组a中都不存在number
*/
return -1;
}</pre><p>注意这个算法有一个非常重要的前提－－<code class="literal">a</code>是排好序的。缺了这个前提，“<span class="quote">如果<code class="literal">a[mid] < number</code>，那么a[start..mid]应该都比<code class="literal">number</code>小</span>”这一步推理就不能成立，这个函数就不能正确地完成查找。从更普遍的意义上说，函数的调用者（Caller）<a id="id2746911" class="indexterm"></a>和函数的实现者（Callee，被调用者）<a id="id2746918" class="indexterm"></a>之间订立了一个契约（Contract）<a id="id2746926" class="indexterm"></a>，在调用函数之前，Caller要为Callee提供某些条件，比如确保<code class="literal">a</code>是排好序的，确保a[start..end]都是有效的数组元素而没有访问越界，这称为Precondition<a id="id2746941" class="indexterm"></a>，然后Callee对一些Invariant进行维护（Maintenance）<a id="id2746950" class="indexterm"></a>，这些Invariant保证了Callee在函数返回时能够对Caller尽到某些义务，比如确保“<span class="quote">如果<code class="literal">number</code>在数组<code class="literal">a</code>中存在，一定能找出来并返回它的位置，如果<code class="literal">number</code>在数组<code class="literal">a</code>中不存在，一定能返回-1</span>”，这称为Postcondition<a id="id2746987" class="indexterm"></a>。如果每个函数的文档都非常清楚地记录了Precondition、Maintenance和Postcondition是什么，那么每个函数都可以独立编写和测试，整个系统就会易于维护。这种编程思想是由Eiffel语言的设计者Bertrand Meyer提出来的，称为Design by Contract（DbC）<a id="id2747004" class="indexterm"></a>。</p><p>测试一个函数是否正确需要把Precondition、Maintenance和Postcondition这三方面都测试到，比如<code class="literal">binarysearch</code>这个函数，即使它写得非常正确，既维护了Invariant也保证了Postcondition，如果调用它的Caller没有保证Precondition，最后的结果也还是错的。我们编写几个测试用的Predicate函数，然后把相关的测试插入到<code class="literal">binarysearch</code>函数中：</p><div class="example"><a id="id2747035"></a><p class="title"><b>例 11.5. 带有测试代码的折半查找</b></p><div class="example-contents"><pre class="programlisting">#include <stdio.h>
#include <assert.h>
#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };
int is_sorted(void)
{
int i;
for (i = 1; i < LEN; i++)
if (a[i-1] > a[i])
return 0;
return 1;
}
int mustbe(int start, int end, int number)
{
int i;
for (i = 0; i < start; i++)
if (a[i] == number)
return 0;
for (i = end+1; i < LEN; i++)
if (a[i] == number)
return 0;
return 1;
}
int contains(int n)
{
int i;
for (i = 0; i < LEN; i++)
if (a[i] == n)
return 1;
return 0;
}
int binarysearch(int number)
{
int mid, start = 0, end = LEN - 1;
assert(is_sorted()); /* Precondition */
while (start <= end) {
assert(mustbe(start, end, number)); /* Maintenance */
mid = (start + end) / 2;
if (a[mid] < number)
start = mid + 1;
else if (a[mid] > number)
end = mid - 1;
else {
assert(mid >= start && mid <= end
&& a[mid] == number) /* Postcondition 1 */
return mid;
}
}
assert(!contains(number)); /* Postcondition 2 */
return -1;
}
int main(void)
{
printf("%d\n", binarysearch(5));
return 0;
}</pre></div></div><br class="example-break" /><p><code class="literal">assert</code>是头文件<code class="literal">assert.h</code>中的一个宏定义，执行到<code class="literal">assert(is_sorted())</code>这句时，如果<code class="literal">is_sorted()</code>返回值为真，则当什么事都没发生过，继续往下执行，如果<code class="literal">is_sorted()</code>返回值为假（例如把数组的排列顺序改一改），则报错退出程序：</p><pre class="screen">main: main.c:33: binarysearch: Assertion `is_sorted()' failed.
Aborted</pre><p>在代码中适当的地方使用断言（Assertion）<a id="id2747104" class="indexterm"></a>可以有效地帮助我们测试程序。也许有人会问：我们用几个测试函数来测试<code class="literal">binarysearch</code>，那么这几个测试函数又用什么来测试呢？在实际工作中我们要测试的代码绝不会像<code class="literal">binarysearch</code>这么简单，而我们编写的测试函数往往都很简单，比较容易保证正确性，也就是用简单的、不容易出错的代码去测试复杂的、容易出错的代码。</p><p>测试代码只在开发和调试时有用，如果正式发布（Release）<a id="id2747134" class="indexterm"></a>的软件也要运行这些测试代码就会严重影响性能了，如果在包含<code class="literal">assert.h</code>之前定义一个<code class="literal">NDEBUG</code>宏（表示No Debug），就可以禁用<code class="literal">assert.h</code>中的<code class="literal">assert</code>宏定义，这样代码中的所有<code class="literal">assert</code>测试都不起作用了：</p><pre class="programlisting">#define NDEBUG
#include <stdio.h>
#include <assert.h>
...</pre><p>注意<code class="literal">NDEBUG</code>和我们以前使用的宏定义有点不同，例如<code class="literal">#define N 20</code>将<code class="literal">N</code>定义为20，在预处理时把代码中所有的标识符<code class="literal">N</code>替换成20，而<code class="literal">#define NDEBUG</code>把<code class="literal">NDEBUG</code>定义为空，在预处理时把代码中所有的标识符<code class="literal">NDEBUG</code>替换成空。这样的宏定义主要是为了用<code class="literal">#ifdef</code>等预处理指示测试它定义过没有，而不是为了做替换，所以定义成什么值都无所谓，一般定义成空就足够了。</p><p>还有另一种办法，不必修改源文件，在编译命令行加上选项<code class="literal">-DNDEBUG</code>就相当于在源文件开头定义了<code class="literal">NDEBUG</code>宏。宏定义和预处理到<a class="xref" href="ch21.html#prep">第 21 章 <i>预处理</i></a>再详细解释，在<a class="xref" href="ch21s04.html#prep.other">第 4 节 “其它预处理特性”</a>将给出<code class="literal">assert.h</code>一种实现。</p><div class="simplesect" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h3 class="title"><a id="id2747272"></a>习题</h3></div></div></div><p>1、本节的折半查找算法有一个特点：如果待查找的元素在数组中有多个则返回其中任意一个，以本节定义的数组<code class="literal">int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };</code>为例，如果调用<code class="literal">binarysearch(2)</code>则返回3，即<code class="literal">a[3]</code>，而有些场合下要求这样的查找返回<code class="literal">a[1]</code>，也就是说，如果待查找的元素在数组中有多个则返回第一个。请修改折半查找算法实现这一特性。</p><p>2、编写一个函数<code class="literal">double mysqrt(double y);</code>求<code class="literal">y</code>的正平方根，参数<code class="literal">y</code>是正实数。我们用折半查找来找这个平方根，在从0到<code class="literal">y</code>之间必定有一个取值是<code class="literal">y</code>的平方根，如果我们查找的数<code class="literal">x</code>比<code class="literal">y</code>的平方根小，则x<sup>2</sup><y，如果我们查找的数<code class="literal">x</code>比<code class="literal">y</code>的平方根大，则x<sup>2</sup>>y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x<sup>2</sup>-y|<0.001），就可以认为找到了<code class="literal">y</code>的平方根。思考一下这个算法需要迭代多少次？迭代次数的多少由什么因素决定？</p><p>3、编写一个函数<code class="literal">double mypow(double x, int n);</code>求<code class="literal">x</code>的<code class="literal">n</code>次方，参数<code class="literal">n</code>是正整数。最简单的算法是：</p><pre class="programlisting">double product = 1;
for (i = 0; i < n; i++)
product *= x;</pre><p>这个算法的时间复杂度是Θ(n)。其实有更好的办法，比如<code class="literal">mypow(x, 8)</code>，第一次循环算出x·x=x<sup>2</sup>，第二次循环算出x<sup>2</sup>·x<sup>2</sup>=x<sup>4</sup>，第三次循环算出<sup>4</sup>·x<sup>4</sup>=x<sup>8</sup>。这样只需要三次循环，时间复杂度是Θ(lgn)。思考一下如果<code class="literal">n</code>不是2的整数次幂应该怎么处理。请分别用递归和循环实现这个算法。</p><p>从以上几题可以看出，折半查找的思想有非常广泛的应用，不仅限于从一组排好序的元素中找出某个元素的位置，还可以解决很多类似的问题。<a class="xref" href="bi01.html#bibli.pearls" title="Programming Pearls">[<abbr class="abbrev">编程珠玑</abbr>]</a>对于折半查找的各种应用和优化技巧有非常详细的介绍。</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11s05.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch11.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch12.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">5. 线性查找 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 第 12 章 栈与队列</td></tr></table></div></body></html>