经过前三章，问题定义分析——算法设计——数据结构选择，这部分主要是编写正确的代码（包括伪代码）
1.问题：二分搜索
这部分一直都以二分搜索为核心进行讲述，自己写的函数如下：
template<typename T> int bsearch(T *A, int l, int h, T obj) { if(l > h) return -1; int mid = (l+h)/2; if(A[mid] == obj) return mid; if(A[mid] > obj) return bsearch(A, l, mid-1, obj); else return bsearch(A, mid+1, h, obj); }
改为迭代方式：
template<typename T> int bsearch2(T*A, int l, int h, T obj) { while(l <= h) { int mid = (l+h)/2; if(A[mid] == obj) return mid; if(A[mid] > obj) h = mid-1; else l = mid+1; } return -1; }
2.编写伪代码，类似与迭代式，并利用循环不变式（初始化，终止，保持三个性质）对过程进行了详尽分析。证明了伪代码的正确性
3.原理
这部分一直强调 断言 与 程序验证。 个人理解，
断言：就是一些合理的推论，我们根据一定的已知条件，做出断言（也就是推出未知条件）。所以进行什么样的断言 决定了程序是否正确，以及程序的走向。
函数：要验证一个函数，需要两个断言：一个是前置条件——调用函数之前就应该成立的状态；一个是后置条件——由函数在终止执行是保证。所以如果一个函数能够保证在前置条件满足时调用它，能够确立后置条件。那么函数就是正确的。
4.习题
4.2寻找第一次出现或最后一次出现的p
4.6问题描述：一个咖啡罐中有一些黑豆和白豆，另有一堆额外的黑豆，重复下面过程，知道罐中只剩一个豆子为止：
从罐中随机取两颗豆子，若颜色相同，将两个都扔掉，放入一个额外的黑豆；
若颜色不同，放回白豆，扔掉黑豆。
证明这个过程会终止，分析最后罐中豆子的颜色？
因为每次豆子总数会减少1，所以过程一定会终止。而每次白豆都是扔掉两个或0个，所以白豆的奇偶性不会改变，故 最后一个豆子要想是白豆，那么必须保证开始罐中有奇数个白豆。
4.7这个问题可以转化为一个相似的常见问题，因为对一个确定的x，其y值是已经排好序的，所以 直接从该点画一条垂直于x轴的竖线，点在该竖线上，并且y已排好序，对其y值进行二分搜索，到最后 l+1 == h 时，点就在此时的l和h表示的区间内。
计算步骤如下：
1）对x，计算y0,y1,...yn-1。后面n个数组成一个有序数组Y
2）在有序数组Y中对y进行二分搜索
int bsearch(int *Y, int N, int y) { int up, down; //分别表示y点在up的上方，或down的下方 l = up = 0; h = down = n-1; while(l <= h) { int mid = (l+h)/2; if(A[mid] == obj) { up = down = obj; return (up, down); } if(A[mid] > obj) { h = mid-1; down = mid; } else { l = mid+1; up = mid; } } if(down == 0) return (-#, 0); if(up == n-1) return (n-1, #); }