在 bsearch() 中自定义比较

发布于 2024-08-26 17:15:22 字数 364 浏览 10 评论 0原文

我有一个指向整数的地址数组（这些整数按升序排列）。它们有重复的值。例如：1， 2, 2, 3, 3, 3, 3, 4, 4......

我试图获取所有大于a的值一定的值（键）。目前正在尝试使用二进制来实现它搜索算法 -

void *bsearch(
 const void *key,
 const void *base,
 size_t num,
 size_t width,
 int ( __cdecl *compare ) ( const void *, const void *)
);

我无法完全实现这一点，但对于其中一些算法来说。

是否有其他方法可以获取所有值数组，而不改变我正在使用的算法？

原文

I have an array of addresses that point to integers ( these integers
are sorted in ascending order). They have duplicate values. Ex: 1,
2, 2, 3, 3, 3, 3, 4, 4......

I am trying to get hold of all the values that are greater than a
certain value(key). Currently trying to implement it using binary
search algo -

void *bsearch(
 const void *key,
 const void *base,
 size_t num,
 size_t width,
 int ( __cdecl *compare ) ( const void *, const void *)
);

I am not able to achieve this completely, but for some of them.

Would there be any other way to get hold of all the values of the
array, with out changing the algorithm I am using?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

念三年u 2024-09-02 17:15:22

正如 Klatchko 和 GMan 所指出的，STL 函数完全满足您的要求： std ::上限。

不过，如果您需要坚持使用 bsearch，最简单的解决方案可能是向前迭代，直到达到新值。

void* p = bsearch(key, base, num, width, compare);
while ((p != end) &&           // however you define the end of the array - 
                               // base + num, perhaps?
       (compare(key, p)==0)){  // while p points to an element matching the key

   ++p; // advance p
}

如果您想获取第一个与 key 匹配的 p，而不是第一个较大的 p，只需使用 --p 而不是 ++p。

正如迈克尔建议的那样，您是否喜欢这种搜索还是重复的二分搜索取决于数组的大小以及您期望的重复次数。

现在，您的问题标题指的是自定义比较函数，但据我了解，这个问题在这里对您没有帮助 - 比较函数必须将任何两个等效对象比较为等效，因此对于识别几个等效对象中的哪一个没有好处是数组中该类型的第一个/最后一个。除非您遇到不同的问题，特别是关于比较函数的问题？

As Klatchko and GMan have noted, the STL function gives you exactly what you're asking: std::upper_bound.

If you need to stick with bsearch, though, the simplest solution may be to iterate forwards until you reach a new value.

void* p = bsearch(key, base, num, width, compare);
while ((p != end) &&           // however you define the end of the array - 
                               // base + num, perhaps?
       (compare(key, p)==0)){  // while p points to an element matching the key

   ++p; // advance p
}

If you want to get the first p that matches key, rather than the first one that's larger, just use --p instead of ++p.

Whether you prefer this or a repeated binary search, as Michael suggests, depends on the size of the array and how many repetitions you expect.

Now, your question title refers to customizing the compare function, but as I understand the question that won't help you here - the compare function must compare any two equivalent objects as being equivalent, so it's no good for recognizing which of several equivalent objects is the first/last of its type in an array. Unless you had a different problem, specifically concerning the compare function?

回复收藏 0 原文

献世佛 2024-09-02 17:15:22

您应该查看 std::upper_bound

例如，要查找第一个值> 3：

const int data[] = { 1, 2, 2, 3, 3, 3, 3, 4, 4, ... };
size_t data_count = sizeof(data) / sizeof(*data);

const int *ptr = std::upper_bound(data, data + data_count, 3);

// ptr will now point to the address of the first 4

相关函数是std::lower_bound。

You should look into std::upper_bound

For example, to find the address of the first value > 3:

const int data[] = { 1, 2, 2, 3, 3, 3, 3, 4, 4, ... };
size_t data_count = sizeof(data) / sizeof(*data);

const int *ptr = std::upper_bound(data, data + data_count, 3);

// ptr will now point to the address of the first 4

A related function is std::lower_bound.

回复收藏 0 原文