如何在数组bsearch（）中找到插入点？
在C（标准库）中使用bsearch（）可以快速找到排序数组中的条目。
但是，如何计算插入新条目的位置（使用标准库）？
bsearch（）专门检查找到的项的键是否等于传递的键，如果不是，则返回NULL – 因此不能使用它。
从问题中不清楚，但可能这是你想要的：
你可以这样做，在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
样本比较function代码是
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) 。
不确定你的意思是“计算插入位置”; 你构建一个数组，然后使用qsort()对其进行排序，然后使用bsearch()进行（很多）搜索。
换句话说：对于典型用法，您不需要实现数组排序，因为标准库也包含该function。
这里不确定连接到bisecting。
更新 ：从评论中，您似乎关心的是插入到您正在进行搜索的数组中。 我建议查看一些对插入更友好的其他数据结构，例如哈希表。 通过不依赖于排序来保持快速搜索，哈希表可能表现更好。 插入到数组中涉及移动所有后续元素，这也是非常昂贵的并且例如哈希表不需要。
更新2 ：要实际尝试回答您的问题，假设您的n个条目array有一个bsearch() – comparator() compare comparator()函数，新项目ni的索引应该由以下内容给出：
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. */
这是@phoxis的答案的改进，它将通过避免任何全局变量使代码线程安全且可重入。 诀窍是使用密钥本身来存储上次访问的地址。
bsearch_insertion.h
#include #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 #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; }
因为insert导致数组尾部的复制，所以时间为O（n）。 如此简单的线性搜索不会大大减慢您的代码速度。 如果从arrays末尾开始搜索，您甚至可以在搜索过程中复制项目。