c++ - 在 bsearch() 中自定义比较

Question

我有一个指向整数的地址数组(这些整数升序排列)。它们具有重复值。例如:1，2、2、3、3、3、3、4、4……

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

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

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

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

Answer 1

正如 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 所建议的，您是喜欢这种还是重复的二分查找，取决于数组的大小和您期望的重复次数。

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