c - 如何在 bsearch() 工作的数组中找到插入点？

Question

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

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

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

Answer 1

问题不清楚，但可能这就是您想要的:

您可以像这样在数组中找到 bsearch () 找到匹配项的索引。

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

编辑

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

好在手册上说:

The compar routine is expected to have two arguments which point to the key object and to an array member, in that order, and should return an integer less than, equal to, or greater than zero if the key object is found, respectively, to be less than, to match, or be greater than the array member.

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