2

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

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

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

我无法完全做到这一点，但对于其中一些人来说。

在不改变我正在使用的算法的情况下，还有其他方法可以获取数组的所有值吗？

4

4 回答 4

2

正如 Klatchko 和 GMan 所指出的，STL 函数为您提供了您所要求的内容：std::upper_bound。

但是，如果您需要坚持使用 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.

正如 Michael 所建议的那样，您是喜欢这个还是重复的二进制搜索取决于数组的大小以及您期望的重复次数。

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

于 2010-03-24T05:52:16.183 回答
1

你应该看看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。

于 2010-03-24T05:28:24.713 回答
1

是的，您可以使用二进制搜索。诀窍是当您找到具有给定键的元素时您会做什么...除非您的下索引和上索引相同，否则您需要在间隔的左侧继续二进制搜索...也就是说，您应该移动上限为当前中点。这样，当您的二分搜索终止时，您将找到第一个这样的元素。然后只需迭代其余部分。

于 2010-03-24T05:36:22.103 回答
0

如果您实现了二叉搜索树，则可以使用树遍历算法来执行此操作。您可以到达所需的“上限”节点，然后简单地从那里按顺序遍历。遍历比多次搜索树更简单，即遍历n个节点的树最多需要n次操作，而搜索n次需要(n.log n)次操作。

于 2010-03-24T06:41:29.780 回答