linux源码中的二分法：lib/bsearch.c

在Linux4.4内核lib目录下的bsearch.c文件给出了内核中的二分查找算法，只有一个函数，也很简单，但是很实用，积累下来，方便以后用的时候直接拿过来使用。此函数用于在已经升序的数组中找到给定目标，关键是利用数组首地址和元素的地址偏移来进行操作，有5个参数：

@key：要查找目标的指针；

@base：升序数组的首地址

@num：升序数组的元素个数

@size：每个元素的大小，即每个元素占多少字节

@cmp：数组元素之间的比较函数指针，这个比较函数需要自己实现，不同的类型使用不同的比较方法。

函数代码如下：

#include <linux/export.h>
#include <linux/bsearch.h>

/*
 * bsearch - binary search an array of elements
 * @key: pointer to item being searched for
 * @base: pointer to first element to search
 * @num: number of elements
 * @size: size of each element
 * @cmp: pointer to comparison function
 *
 * This function does a binary search on the given array.  The
 * contents of the array should already be in ascending sorted order
 * under the provided comparison function.
 *
 * Note that the key need not have the same type as the elements in
 * the array, e.g. key could be a string and the comparison function
 * could compare the string with the struct's name field.  However, if
 * the key and elements in the array are of the same type, you can use
 * the same comparison function for both sort() and bsearch().
 */
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;

		result = cmp(key, base + mid * size);//寻找目标和数组中间值比较
		if (result < 0)
			end = mid;//如果寻找目标小于中间值，则目标在开始和中间之间
		else if (result > 0)
			start = mid + 1;//如果寻找目标大于中间值，则目标在中间和结束之间
		else
			return (void *)base + mid * size;//若相等则找到目标
	}

	return NULL;
}

写了个小例子来验证，在一个已经排好序的数组中来查找给定目标值，元素为int类型，以此来掌握此函数接口的使用的方法，代码如下

#include <stdlib.h>
#include <stdio.h>

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;

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

    return NULL;
}
//compare function
int compare(const void *key, const void *elt){
    int *a = (int *)key;
    int *b = (int *)elt;

    if(*a < *b){
        return -1;
    }else if( *a > *b){
        return 1;
    }
    
    return 0;    
}

int main(){
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int size = sizeof(arr)/sizeof(arr[0]);
    int key = 21;
    int *target = (int *)bsearch((void *)&key, (void *)arr, size, sizeof(int), compare);

    if(target != NULL){
        printf("find target : %d\n", *target);
    }else{
        printf("cannot find the target: %d!\n", key);
    }

    int key1 = 7;
    int *target1 = (int *)bsearch((void *)&key1, (void *)arr, size, sizeof(int), compare);

    if(target1 != NULL){
        printf("find target1 : %d\n", *target1);
    }else{
        printf("cannot find the target1: %d!\n", key1);
    }

    return 0;
}

上面的例子中{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}中首先查找21，明显不存在；然后查找7，存在。运行结果如下：