【习题解答】 对数时间查找

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 6.2 二分查找的区间范围设为，并假定每轮开始时都已经知道以下四个变量的值： + + + +

则比较和的大小以后，可以以的代价更新上面的变量，以进入左半边子区间为例 + + + +

这样把单次的开销降到常数，总的开销就是

6.3

思路是对递归定义使用数学归纳法，以证明始终符合直接定义。

直接定义： + 根黑色，叶黑色 + 红色节点不连续出现 + 任意节点为根的子树，叶的黑色深度相等，该深度即红黑树的黑色高度

递归定义： + 基本情况，，即一颗黑色根，显然满足直接定义，黑色高度是0 + 归纳推理，若都是满足红黑树直接定义。由递归定义知的根是红色，左右子树都是； 的根是黑色，左右子树是或。然后验证是否满足那三条直接定义即可

6.4

分为内部黑色节点、内部节点、高度三个部分来证明，每次用数学归纳法同时证明和的情况。

1. 首先证有不少于个内部黑色节点，有不少于个内部黑色节点

• 基本情况：，有0个内部黑色节点；，有0个内部节点，有1个内部黑色节点
• 归纳推理：假设，有至少个内部黑色节点，有至少个内部黑色节点，则时，有至少内部黑色节点，有至少内部黑色节点
• 故对于任意非负整数，有至少个内部黑色节点，有至少个内部黑色节点。

2. 然后证有不超过个内部节点，有不超过个内部节点

• 基本情况：，有0个内部节点；，有1个内部节点，最多有3个内部节点
• 归纳推理：假设，有不超过个内部节点，有不超过个内部节点，则时，有最多内部节点，有最多内部节点
• 故对于任意非负整数，有不超过个内部节点，有不超过个内部节点

3. 最后证明任意黑色节点的普通高度至多是该节点黑色高度的2倍，任意黑色节点的普通高度至多是该节点黑色高度的2倍

• 先用数学归纳法，证的根的黑色高度是且的根的叶子的黑色高度是
• 然后再用数学归纳法，证的根的普通高度最多是，的根的普通高度最多是
• 由此可知，无论是还是，其中任何黑色节点的普通高度至多是黑色高度的2倍。

6.5

• 考虑到是非严格单调增的
• 检查和是不是0，以及是否满足零点存在性定理，复杂度可判断是否存在
• 如果存在解，二分查找，复杂度找到具体下标

6.8

(1)

遍历一次，找到最大值和最小值，复杂度

(2)

有序数组，直接取两端即可，复杂度

(3)

看到要求复杂度是，自然想到进行排序，然后遍历相邻两个元素的差的绝对值，找到最小的且非0的即可。

(4)

相当于第(3)问的一个部分，进行一层遍历，即计算相邻两个元素的差的绝对值，找到最小的且非0的即可。

6.14

(1)

假设不存在，由，矛盾。

(2)

• 二分查找，每次找区间的中间的两个数进行比较，假设是
• 如果，则以子区间(L,i+1)继续查找
• 如果，则以子区间(i,R)继续查找
• 可以证明算法的正确性，用数学归纳法
• 二分查找，每次排除一半区间，复杂度