Lesson-41.md

March 18, 2014 · View on GitHub

Lesson 41 - BSearch 实现

课程任务

在 《C程序设计语言》书第3.3小节中，介绍了一个折半查找函数 binsearch()，如下所示：

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */  
int binsearch(int x, int v[], int n)
{
        int low, high, mid;
        low = 0;
        high = n - 1;
        while (low <= high) {
                mid = (low+high)/2; 
                if (x < v[mid])
                        high = mid - 1; 
                else if (x > v[mid])
                        low = mid + 1;
                else /* found match */
                        return mid;
        }   
        return -1; /* no match */  
}

请参照这个算法思想，实现标准库函数中 bsearch 函数。

#include <stdlib.h>

void *
bsearch(const void *key, const void *base, size_t nel, size_t width,
		int (*compar) (const void *, const void *));

参考资料