5

在 C（标准库）中使用 bsearch() 可以快速找到排序数组中的条目。

但是，我如何计算插入新条目的位置（使用标准库）？

bsearch() 专门检查找到的项目的键是否等于传递的键，如果不是，则返回 NULL - 所以不能使用它。

4

4 回答 4

5

从问题中不清楚，但可能这就是你想要的：

您可以执行类似的操作来查找bsearch ()找到匹配项的数组中的索引。

if (bsearch_returned_address != NULL)
  index = (bsearch_returned_address - array_base_address)

编辑

要知道 bsort 上次访问的位置，请查看以下内容。

好在手册说：

比较例程应该有两个参数，它们依次指向键对象和数组成员，如果找到键对象，则应分别返回一个小于、等于或大于零的整数，以小于、匹配或大于数组成员。

因此，您可以将比较函数中的第二个参数存储在全局变量中，并在失败的情况下使用此变量中的地址，该地址指向bsearch函数访问以查找匹配项的最后位置。

例如：

带有地址和值的列表：

[0x8d6010: 0][0x8d6014: 4][0x8d6018: 8][0x8d601c: 12][0x8d6020: 16][0x8d6024: 20][0x8d6028: 24][0x8d602c: 28][0x8d6030: 32][0x8d6034: 36]

搜索价值

13

输出

fmem: (nil)  //this is the memory location where it was found
last_mem1: 0x7fff8c8e6c54 //last val of 1st param of compare
last_mem2: 0x8d601c //last val of 2nd param of compare
*last_mem1: 13,        *last_mem2: 12

示例比较功能代码是

static const int *last_mem1, *last_mem2;

static int
compmi(const void *a, const void *b)
{
    last_mem1 = a; last_mem2 = b;
    return *(int *)a - *(int *)b;
}

所以你可以在地址后面插入last_mem2。虽然有终端情况，但如果你找到一个小于第一个元素的键，那么last_mem2也会有第一个元素的地址。

但是，您必须如何移动数组元素来为插入腾出位置，这将使插入复杂度达到O(n). 您可能希望通过引入某种惰性插入来提高性能，例如创建一个单独的无序列表，它比原始列表小得多，并在那里转储新元素。搜索时，bsearch在原始列表中执行，在转储中进行线性搜索。当转储列表增长超过某个阈值时，您可以通过执行插入排序来合并列表。但是，你仍然不能O(lg n)。

于 2012-06-28T12:59:47.097 回答
4

这是对@phoxis 答案的改进，它将通过避免任何全局变量来使代码成为线程安全和可重入的。诀窍是使用密钥本身来存储上次访问的地址。

bsearch_insertion.h

#include <stdlib.h>

#ifndef BSEARCH_INSERTION_H
#define BSEARCH_INSERTION_H

/* Just like bsearch(3), but return a pointer to the element after which
 * the key would need to be inserted in order to maintain sorted order. */
void *bsearch_insertion(
    const void *key, const void *base, size_t nel,
    size_t width, int (*compar)(const void *, const void *));

#endif /* BSEARCH_INSERTION_H */

bsearch_insertion.c

#include "bsearch_insertion.h"

typedef struct
{
    const void *key;
    int (*const compar)(const void *, const void *);
    void *last_visited;
} bsearch_insertion_state;

static int bsearch_insertion_compare(const void *a, const void *b)
{
    bsearch_insertion_state *state = (bsearch_insertion_state *) a;
    state->last_visited = (void *) b;
    return state->compar(state->key, b);
}

void *bsearch_insertion(
    const void *key, const void *base, size_t nel,
    size_t width, int (*compar)(const void *, const void *))
{
    bsearch_insertion_state state = {key, compar, NULL};
    bsearch(&state, base, nel, width, bsearch_insertion_compare);
    return state.last_visited;
}

示例：test.c

#include <stdio.h>
#include "bsearch_insertion.h"

static int cmp(const void *a, const void *b)
{
    int aint = *(const int *)a;
    int bint = *(const int *)b;
    return aint - bint;
}

int main(int argc, char **argv)
{
    int data[] = {0, 1, 2, 3, 5};
    int key = 4;
    void *result = bsearch_insertion(
        &key, data, sizeof(data) / sizeof(data[0]), sizeof(data[0]), cmp);
    /* Should print "Insertion point: 3" */
    printf("Insertion point: %d\n", (int *)result - data);
    return 0;
}
于 2016-10-25T16:37:58.983 回答
3

不确定“计算插入位置”是什么意思；您构建一个数组，然后使用 对其进行排序qsort()，然后使用bsearch().

换句话说：对于典型用法，您不需要实现数组排序，因为标准库也包含用于此的功能。

不确定这里与二等分的联系。

更新：从评论中，您似乎担心插入到您也在进行搜索的数组中。我建议查看其他对插入更友好的数据结构，例如哈希表。通过不依赖排序来保持快速搜索，哈希表可能会执行得更好。插入数组涉及移动所有后续元素，这也非常昂贵，并且对于例如哈希表来说是不需要的。

更新 2：要实际尝试回答您的问题，假设您的条目具有bsearch()-compariblecomparator()函数，则新项目的索引应由以下内容给出：arraynni

size_t i;

for( i = 0; i < n && comparator(&ni, array + i) >= 0; ++i )
  ;
/* Grow array, copy i..n to (i+1)..(n+1), insert ni at i. */
于 2012-06-28T12:55:46.047 回答
1

因为插入导致复制数组尾部，所以时间是O(n)。所以简单的线性搜索不会显着减慢你的代码。如果您从数组末尾开始搜索，您甚至可以在搜索期间复制项目。

于 2012-06-28T13:26:42.853 回答