linux内核中的二分查找

  二分查找也叫折半查找，折半查找就是利用表中元素的有序性，每经过一次比较就把表中的查找范围缩小一半，而且查找结果产生于最后查找的表元素中，很显然，它属于减冶算法。具体算法如下：

int bisearch(int x,NODE *elem,int len)
{
int left,right,mid;
left = 0;
right = len-1;
while(left <= right){
mid = (left + right)/2;
if(elem[mid].key < x) left = mid + 1;
else if(elem[mid].key > x) right = mid - 1;
else return mid;
}
return NOT_FOUND;
}

内核中的二分查找如下代码：

void *bsearch(const void *key, const void *base, size_t num, size_t size,
          int (*cmp)(const void *key, const void *elt))
{
    size_t start = 0, end = num;
    int result;

    while (start < end) {
        size_t mid = start +(end - start) / 2;     (1)

        result = cmp(key, base +   mid * size);     （2）
        if (result < 0)
            end = mid;
        else if (result > 0)
            start = mid +   1;
        else
            return (void *)base +   mid * size;
    }

    return NULL;
}
EXPORT_SYMBOL(bsearch);

大家仔细分析这两段代码还是有区别的.(1)没有采用left和right相加之后再除以2，是为了防止溢出，因为我们谁也无法预料要查找的表的数到底有多大。

 （2）处用比较的方式通过参数传进来，可以由用户自由编写。

   我们可以自己写一个用户态的程序复用内核中的代码。其中参数分别代表：key是我们要查找的元素，base是链表的首地址，num是链表的总长度，size是每个元素的平均大小。cmp是用户自己定义的比较函数。