如何在数组 bsearch() 上找到插入点？

Question

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

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

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

Answer 1

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

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

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

编辑

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

好消息是手册上说：

所述COMPAR例程预计将有两个参数，其点到密钥对象和阵列构件，以该顺序，并且应当返回一个整数小于，等于，或如果密钥对象被发现，分别大于零，来小于、匹配或大于数组成员。

因此，您可以将比较函数中的第二个参数存储在全局变量中，并在失败的情况下使用此变量中的地址，该地址指向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)。

Answer 2

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

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;
}

示例：测试.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;
}