二分查找、区间、一致性

据说90%的程序员不能正确实现二分查找,《编程之美》里也专门有一章是来讨论二分查找的。因为要重启小组内的learning group,和同事讨论了一下,就拿二分查找来kick-off。基本来说,大家的实现都有这样那样的问题,甚至题目本身给出的函数原型都错了!

实现的要求是,假定整数数组array是从小到大排序的,查找key是否在array中,如果存在则返回其index,否则返回-1。我随手就写了一个函数的原型,

int bin_search (int *array, size_t len, int key)

当时没有仔细考虑,size_t和int表示的范围是不同的,会有溢出的问题。

基本上有两种实现的方法,一种是在[begin, end]闭区间上进行迭代(end是最后一个元素的index,即begin+len-1),找到一个中点middle之后,将区间划分为[begin, middle-1]和[middle+1, end],子区间依然是闭区间(且不包括middle);因为整数区间[begin, begin]不是空区间(包括begin这个整数),所以迭代的终止条件是begin>end。

第二种方法是在[begin, end)这个半闭半开区间上进行迭代(end为begin+len),找到一个中点middle之后,将区间划分为[begin, middle)和[middle+1, end),子区间依然是半闭半开区间(且不包括middle);因为整数区间[begin, begin)是个空区间,所以迭代的终止条件是begin==end。这种实现方式和STL中容器的迭代器是很一致的 :)

子问题和父问题保持一致性,对正确的实现二分查找来说是至关重要的。如果把握住子区间划分的正确性,自然能保证好迭代终止条件的正确性。(说来惭愧,我就曾用第二种方法时不小心把子区间的边界写错了,导致死循环。)

最后一点要注意的是,找中点时不要溢出,应该用begin + (end - begin)/2来得到中点的位置。

其实还有一点需要探讨的,就是如果数组的长度不是很长,可能直接循环顺序查找的速度更快。但是去看了solaris libc中的bsearch,并没有这样去“优化”。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha