bsearch函数详解

发布时间：2023-05-19

一、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(log n)。 接下来，我们来分析一下为什么bsearch函数的时间复杂度是O(log n)。假设在第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(log n)。

五、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函数，灵活运用它来处理各种实际问题。

推荐文章