最近有同学面试的时候被要求写一个二分查找的函数，老生常谈的问题了，不过要写正确还是没那么简单的。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）的复杂度。
我的同学有写对吗？我还是有些怀疑:)
