重谈二分查找

    最近有同学面试的时候被要求写一个二分查找的函数，老生常谈的问题了，不过要写正确还是没那么简单的。Knuth的文章里曾提到过，二分查找的概念早在1946年就已经提出，但第一个正确的二分查找程序直到1962年才出现。很多库的实现里都包含有bug，包括java.util。Programming Pearls的作者Jon Bentley曾说过他曾要求一批专业的程序员写出二分查找函数，但在充足时间下仅仅只有极少数人的代码是正确的,看来真的没想像中的容易哦。感兴趣的可以看看这个链接

typedef int (*usrCompareFun)(const void *key1, const void *key2);

/* binary search */
int myBinarySearch(void *array, const void *target, usrCompareFun cmp,
                        size_t element, size_t total)
{
    int left, right, middle;
    left = 0;
    right = total -1;

    while (left <= right)
    {
        middle = left + (right - left) / 2;
        switch (cmp(((char *)array + middle * element), target))
        {
            case -1:
                right = middle - 1;
                break;

            case 1:
                left = middle + 1;
                break;

            case 0:
                return middle;
        }
    }
    return -1;
}

以上是我的代码，对于面试题来讲，大多数人可能会直接写一个查找整型数据的函数。但作为专业程序员，永远记住要设计通用的函数。C++程序员会用模板来解决数据类型的问题，但作为纯C程序员则callback函数的使用就是唯一的选择，这也能让面试官有一个好的印象，在面试中多展现自己的能力总不是坏事。

值得注意的是 middle = left + (right - left) / 2;这一句代码。很多库的实现里是这样写的： middle = (left + right) / 2，这会有一个问题，那就是当left + right超过整数范围时会溢出，这时middle的值会异常，再通过middle做下标访问数组中的数据时就会产生不可预料的结果，C中通常会直接Segmentation fault。很不起眼的地方吧，众多库的实现者也不能幸免。上面的代码还是有一个问题，那就是当数组中的数据出现多个相同的值时，返回的并不是第一个出现的位置，比如极端情况下，当数组中所有数据都相同时，查找到后返回的就是数组中间位置的下标而不是第一个，这在某些情况下也会产生问题。

wikipedia上有解决方法，避免了早期查找成功即返回索引，但同时仍可以达到lg（N）的复杂度。

我的同学有写对吗？我还是有些怀疑:)

Ubuntu10.04上安装Trac

Trac是一个开源的，基于web的项目管理和bug追踪的工具。Trac由Edgewall Software负责开发，完全由python编写而成。我之前所在的公司也是用Trac来做项目管理，甚至员工的绩效都可以用Trac来做管理哦。因为CC同学正在艰苦创业中，这次回来跟他聊天聊到版本管理工具，目前CC同学的情况比较惨，基本上程序都是他一个人在维护，没有用到任何的项目管理和源码版本管理工具，时间长了一定会非常混乱，也不利于今后他新招的程序员快速熟悉项目。我还是推荐他用Trac，目前也已经提供了对SVN的接口，看起来这就是CC同学所要的项目管理+源码控制了。

我只是在公司用过Trac，自己并没有build一个环境的经验，在这里记录下我安装Trac的经过。至于Trac的详细使用方法，请参考Trac官方使用教程.

我的安装环境是Ubuntu 10.04。

1. Trac的安装教程上说用easy_install安装最为方便，试了一下Ubuntu上没有自带这个安装工具，所以先apt-get install python-setuptools（注意，Trac是用python写的，必须有python的执行环境，Ubuntu 10.04默认安装了python2.6.5，因此如果你没有安装python的话，先去安装咯）

2. 有了easy_install之后，执行easy_install http://svn.edgewall.org/repos/trac/trunk

看的出来，是直接通过SVN下到代码后自动完成安装，因此这里你必须保证已经安装了SVN。（可通过apt-get install subversion安装）

事实上到这里已经安装完了，有安装工具帮忙真的方便很多。下面我想看看有没有安装成功。

首先需要我们指定一个目录用来存放项目的数据，这被称为TracEnvironment。

创建一个新的Trac环境目录可使用如下的命令：

trac-admin /home/colin/trac/ initenv

接下来提示你输入项目的名称，我就用test好了。

然后是提示要求输入Database connection string [sqlite:db/trac.db]> 

Trac默认是使用sqlite做数据库的，这里可以直接输入回车使用默认值。至于如何自定义connection string，请参考Trac的文档。需要根据一定的规则去设定，随意输入会出错哦。

当出现Project enviroment for ‘test' created，表示已经创建好项目的环境了。

可以通过编辑trac.ini文件来定制你的环境。

继续我们的测试，输入tracd -p 8080 /home/colin/trac/这行命令启动了一个轻量的Trac web server，之后我们就可以通过浏览器来访问Trac了！

打开浏览器，在地址栏输入http://localhost:8000/trac如果看到了Trac页面表示已经安装成功了！

Trac的详细的使用方法较复杂，包括权限设定，wiki编辑，版本管理等请参考Trac使用教程。

也可以访问这里查看中文Trac教程。