如何在bsearch()作用的数组中找到插入点?

gcuhipw9  于 2023-08-03  发布在  其他
关注(0)|答案(5)|浏览(105)

在C(标准库)中使用bsearch()可以快速找到排序数组中的条目。
但是,如何计算在何处插入新条目(使用标准库)?
bsearch()专门检查找到的项的键是否等于传递的键,如果不等于,则返回NULL -所以不能使用它。

tktrz96b

tktrz96b1#

问题不清楚,但这可能是你想要的:
您可以执行以下操作来查找bsearch ()找到匹配的数组中的索引。

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

字符串

编辑

要知道bsort上次访问的位置,请查看以下内容。
好消息是手册上说:
compar例程应该有两个参数,分别指向key对象和数组成员,* 按此顺序 *,如果发现key对象分别小于、匹配或大于数组成员,则应返回小于、等于或大于零的整数。
因此,可以将比较函数中的第二个参数存储在一个全局变量中,在失败的情况下使用该变量中的地址,该地址指向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)

yfjy0ee7

yfjy0ee72#

下面是对@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;
}

doinxwow

doinxwow3#

不确定你说的“计算插入位置”是什么意思;构建一个数组,然后使用qsort()对其进行排序,然后使用bsearch()进行(许多)搜索。
换句话说:对于典型的用法,你不需要实现数组排序,因为标准库也包含了它的功能。
我不确定这和二等分有什么联系。

UPDATE:从评论来看,似乎你关心的是对一个数组进行插入,而你也在从中进行搜索。我建议看看其他一些对插入更友好的数据结构,比如哈希表。通过不依赖于排序来保持快速搜索,哈希表可能会执行得更好。插入到阵列中涉及移动所有后续元素,这也是相当昂贵的,并且对于例如以下情况不需要:散列表。
更新2:为了实际回答你的问题,假设你有一个bsearch()可比较的comparator()函数,用于n条目的array,新条目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. */

字符串

5fjcxozz

5fjcxozz4#

时间复杂度是O(n)的。所以简单的线性搜索不会显著降低代码的速度。如果从数组的末尾开始搜索,甚至可以在搜索过程中复制项。

9wbgstp7

9wbgstp75#

@Leo的精彩回答:还有最后一个问题,如果你想让它成功的话,你会碰到的。我刚刚做了:-)
你还需要(如@phoxis所建议的)存储最后一次比较的结果,因为如果新键和最后一次比较的数组元素之间的最后一次比较的结果> 0,则插入点比最后一次比较的数组元素更远一个元素。
因此,为了解决这个问题,将“int last_cmp”添加到bsearch_insertion_state结构中,在比较函数中设置它:

int cmp = state->compar(state->key, b);
state->last_cmp = cmp;
return cmp;

字符串
然后(这可能不是最优雅的方法)将bsearch_insertion()的返回类型从void * 更改为bsearch_insertion_state(即返回整个结构),这样调用者就可以在测试程序中写:

bsearch_insertion_state state = bsearch_insertion(
    &key, data, sizeof(data) / sizeof(data[0]), sizeof(data[0]), cmp);
int *ipptr = state.last_visited;
if( state.last_cmp > 0 ) ipptr++;
int ip = ipptr - data;

// Should print "Insertion point: 4"
printf("Insertion point (insert key at position): %d\n", ip );


[Note:我对插入点的定义与@Leo的定义可能有细微的差别,因此@Leo的版本打印了3,我的版本打印了4 -但根据我的理解,插入点是插入新密钥的位置,即首先你把元素ip.. endofarray向上移动一个,然后你通过data[ip] = key存储密钥。对于此特定测试用例,4是正确的插入点。]
我已经构建了我自己的版本,使用char * 字符串数组和strcmp()进行低级比较,因此我的“ipptr”是char**,并编写了外部shuffle up和insert代码,我可以验证这似乎对我有效,产生正确排序的字符串。

相关问题