3.11　程序改错

一次面试之后，应聘者和面试者微笑着握手告别，但是他们对面试的评价往往相差很远，例如：

应聘者：来了一个比较和气的员工，我们谈了谈各种排序的优劣，我昨天晚上在网上看的东西都用上了，我几乎要把他侃晕了。后来，他要我写一个二分查找的程序，我略加思索，很快地写好了，写得太快了，有一个条件没有考虑，让他看了出来。后来他叫我再检查一下还有什么错，我还是比较自信的，觉得代码没什么大问题。他挑出来一些小小的问题，无外乎一些“牛角尖”的问题，我也很快搞定了……我觉得面试也不过如此。

面试者：我们先谈了谈了谈各种排序的优劣，我发现他混淆了各种排序方法的优缺点和适用范围，叙述得完全没有条理（例如……）。我叫他写一个完整的二分排序。他想了很长时间，最后写出来的解法有一个严重的错误，我指出之后，他能想出一个改正的方法，但不是最优的。我强调“完整的程序”，让他再检查一下还有什么错，他根本不会用一些测试用例去检查，而是把程序又自己读了一遍，说没有错误。我指出了至少4个小错误，他能认识这些错误，但是在修改中把原来算法的结构破坏了，最后的解法显得非常混乱。他在这个题目中花了很长时间……我觉得他明显达不到我们的要求。

二分查找是算法设计的基本功。它的思想很简单：分而治之；即通过把一个大问题分解成多个子问题来降低解题的复杂度。思路固然简单，但是许多人在写代码实现的时候却往往容易出现各种错误。下面是一个程序片段，其中包含了一些常见的错误，这些错误正是我们在写二分查找程序时所应该注意的地方。你能够找出来吗？

问题：找出一个有序（字典序）字符串数组arr中值等于字符串v的元素的序号，如果有多个元素满足这个条件，则返回其中序号最大的。

代码清单3-17　带有错误的二分查找源码

分析与解法

在写循环（或者递归）程序的时候，我们特别应该注意三个方面的问题：初始条件，转化，终止条件。针对上面这个二分程序，我们也要逐一考虑这些方面。

程序的第一个问题就是：midIndex＝（minIndex＋maxIndex）/2；

这样的写法粗看没什么不妥，但在一些极端情况下，会由于求和中间结果的溢出而导致出现错误（假设这是个32位程序，32位有符号整数可以表示的范围是-2147483648～+2147483647，如果minIndex加上maxIndex的值恰好超过了+2147483647，那么就会造成上溢出，导致midIndex变成负数）。所以我们最好把它写成midIndex＝minIndex＋（maxIndex－minIndex）/2；

第二个问题是：循环的终止条件有可能无法到达，也就是说在某些测试用例下，程序不会停止。比如，当minIndex＝2，maxIndex＝3，而arr[minIndex]＜＝v的时候，程序将进入死循环。

所以改正后的代码是：

代码清单3-18　纠正错误后的二分查找源码

你也许会抱怨：“哇，面试这样的问题也太吹毛求疵了吧？”，是的，世界上怕就怕“认真”二字，任何简单的问题认真起来就不再简单。很多让微软和其他公司遭受巨大损失的安全漏洞，就是因为一些看似不错，其实有漏洞的边界条件的检查。

要避免出现类似的问题，需要我们在写程序的时候特别留意这些容易出错的地方。下面列出一些与二分查找相关的常见问题，题目虽然都很简单，但是大家不妨试试看，为每道题写出一个正确的解答：

给定一个有序（不降序）数组arr，求任意一个i使得arr[i]等于v，不存在则返回-1

给定一个有序（不降序）数组arr，求最小的i使得arr[i]等于v，不存在则返回-1

给定一个有序（不降序）数组arr，求最大的i使得arr[i]等于v，不存在则返回-1

给定一个有序（不降序）数组arr，求最大的i使得arr[i]小于v，不存在则返回-1

给定一个有序（不降序）数组arr，求最小的i使得arr[i]大于v，不存在则返回-1

在写完解答之后，请大家不要停止思考，能不能接着为每道题各写出关键的测试用例呢？

扩展问题

下面一个题目是出现在笔试题目中的考题，有人写了一个简单的程序，判断一个单链表是否有环，如果有，把指向环开始的指针返回；如果没有环，返回NULL。

这个程序有不少错误，我们能否在尽量保持原程序框架的基础上，修改这个程序，以得到正确的结果？

代码清单3-19　简单并带有错误的环形单链表检测代码

注释

①　strstr函数说明：

原型：extern charstrstr（charhaystack，char*needle）；

用法：#include<string.h>

功能：从字符串haystack中寻找needle第一次出现的位置（不比较结束符NULL）。

说明：返回指向第一次出现needle位置的指针，如果没找到则返回NULL。