编程技巧仅仅是编写正确程序的很小一部分，更重要的还是前三章的主题：问题定义、算法设计和数据结构选择。
本章节以二分搜索为例子，讲解了如何对程序进行验证及正确性分析。
得出的一般性原理：
 断言。
 顺序控制结构。
 选择控制分支。
 迭代控制结构。每次迭代保持不变式为真。
 函数。使用前置条件和后置条件来验证函数。
习题
2. If the original binary search was too easy for you, try the variant that returns in P the first occurrence of T in the array X (if there are multiple occurrences of T, the original algorithm returns an arbitrary one). Your code should make a logarithmic number of comparisons of array elements; it is possible to do the job in $\log _2N$ such comparisons.
1  class Solution { 
先找到第一个大于等于 target 的下标，然后判断是不是相等。
3. Write and verify a recursive binary search program. Which parts of the code and proof stay the same as in the iterative version, and which parts change?
1  class Solution { 
5. Prove that this program terminates when its input is a positive integer.
1  while x !=1 do 
拉兹猜想又名 3n＋1 猜想或冰雹猜想。不明觉厉！
6. [C. Scholten] David Gries calls this the “Coffee Can Problem” in his Science of programming. You are initially given a coffee can that contains some black beans and some white beans and a large pile of “extra” black beans. You then repeat the following process until there is a single bean left in the can.
Randomly select two beans from the can. If they are the same color, throw them both out and insert an extra black bean. If they are different colors, return the white bean to the can and throw out the black.
Prove that the process terminates. What can you say about the color of the final remaining bean as a function of the numbers of black and white beans originally in the can?
每次都减少一个豆子，最终肯定要仅剩一个豆子。白色豆子都是一对一对的减少，所以如果白色豆子一开始个数是偶数，那么剩下黑色豆子；如果白色豆子个数是奇数，那么剩下白色豆子。
7. A colleague faced the following problem in a problem to draw lines on a bitmapped display. An array of N pairs of reals $\left(a_i, b_i\right)$ defined the N lines $y_i = a_ix + b_i$. The lines were ordered in the xinterval [0, 1] in the sense that $y_i < y_{i+1}$ for all values of $i$ between 1 and N1 and all values of x in [0, 1]:
Less formally, the lines don’t touch in the vertical slabs. Given a point (x, y), where $0\leq x \leq 1$, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?
固定 x 的值，然后比较 $y_0$ 的值，用二分搜索来确定在哪个区间。因为 $y_i$ 已经是排序的，然后找到第一个大于或者等于 $y_0$ 的线段。
1 

8. Binary search is fundamentally faster than sequential search: to search an Nelement table, it makes roughly $\log _2N$ comparisons while sequential search makes roughly $\frac{N}{2}$. While it is often fast enough, in a few cases binary search must be made faster yet. Althought you can’t reduce the logarighmic number of comparisons made by the algotighm, can you rewrite the binary search code to be faster? For definiteness, assume that you are to search a sorted table of N=1000 integers.
将二分扩展成 k 分，比如四分搜索，可以提升速度。