bsearch函数详解

一、bsearch函数

bsearch函数是在已排序的数组中查找指定元素的函数，是C语言标准库函数之一。它的原型如下：

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

bsearch函数接收五个参数：

1. key：指向要查找的元素的指针
2. base：指向有序数组第一个元素的指针
3. nmemb：数组中元素的个数
4. size：每个元素的大小
5. compar：用于比较两个元素大小的函数指针

二、bsearch函数返回什么

bsearch函数返回指向要查找的元素的指针，如果没有找到相应元素，则返回NULL指针。

三、bsearch用法

使用bsearch函数时，需要注意几个问题：

1. 在使用bsearch函数查找某个元素之前，必须保证数组已经排序。否则，查找结果是不可预知的。
2. 比较函数compar需要自己实现，需要根据数组里的元素类型写出相应的比较函数。一般情况下，比较函数需要返回一个整型值：

//比较两个整数的函数
int cmp_int(const void *a, const void *b){
    return (*(int*)a - *(int*)b);
}

四、bsearch研究

我们可以对bsearch函数做一些相关分析。假设有一个长度为n（n>=2）的排序数组，现在要在这个数组中找到一个指定的元素key，那么使用bsearch函数的时间复杂度为O(logn)。

接下来，我们来分析一下为什么bsearch函数的时间复杂度是O(logn)。假设在第k步时，已经剩下r个元素尚未检查，那么有：

• 第1步时，r=n
• 第2步时，r=n/2
• 第3步时，r=n/4
• 第4步时，r=n/8
• 第k步时，r=n/2^k

当r=1时，也就是只有一个元素时，查找结束。所以，k=log2(n)，时间复杂度为O(logn)。

五、bsearch函数c语言

接下来举一个代码例子，对于一个有序的整型数组，使用bsearch函数查找是否存在某个元素：

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

int cmp_int(const void *a, const void *b);

int main(){
    int arr[] = {1, 3, 5, 7, 9};
    int key1 = 3, key2 = 4;
    int *result;
    result = (int*)bsearch(&key1, arr, 5, sizeof(int), cmp_int);
    if(result != NULL){
        printf("%d is found in arr\n", *result);
    }else{
        printf("%d is not found in arr\n", key1);
    }
    result = (int*)bsearch(&key2, arr, 5, sizeof(int), cmp_int);
    if(result != NULL){
        printf("%d is found in arr\n", *result);
    }else{
        printf("%d is not found in arr\n", key2);
    }
    return 0;
}

int cmp_int(const void *a, const void *b){
    return (*(int*)a - *(int*)b);
}

上面的代码中，首先定义了一个整型数组arr，然后使用bsearch函数查找元素2和4。由于数组arr是有序的，元素2并不存在于数组中，第一次查找结果为NULL，第二次查找结果是3，因为3是数组中的一个元素。

六、bsearch 巧妙

其实bsearch函数还可以用来查找满足某个条件的最大或最小的元素。例如，对于一个已经按照某个方式排序的整型数组，找到最后一个小于等于指定元素key的元素位置：

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

int cmp_int(const void *a, const void *b);

int main(){
    int arr[] = {1, 3, 5, 7, 9};
    int key = 6;
    int *result;
    result = (int*)bsearch(&key, arr, 5, sizeof(int), cmp_int);
    if(result == NULL){
        result = arr + 4;
    }
    printf("The last less than or equal to %d element is %d\n", key, *result);
    return 0;
}

int cmp_int(const void *a, const void *b){
    return (*(int*)a - *(int*)b);
}

代码中，当key不存在于数组arr中时，根据bsearch函数的返回值，最后一个小于等于key的元素位置是arr+4的位置。因此，第二个printf语句输出的结果是“The last less than or equal to 6 element is 5”。

类似地，如果需要查找满足某个条件的最小的元素位置，可以将比较函数更改为：int cmp_int_min(const void *a, const void *b) {return (*(int*)a – *(int*)b); }。

七、小结

本篇文章详细讲解了bsearch函数的定义、用法、时间复杂度及相关细节，以及一些巧妙的使用技巧。希望读者可以通过本文深入理解bsearch函数，灵活运用它来处理各种实际问题。