在bsearch（）中自定义比较

我有一个指向整数的地址数组（这些整数按升序排序）。它们具有重复值。例如：1， 2,2,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 *)
);

我无法完全实现这一点，但对于其中一些人来说。是否有任何其他方法来掌握所有的价值观数组，没有更改我正在使用的算法？

已邀请:

4 个回复

舞备联

正如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
}

如果你想获得匹配键的第一个p，而不是第一个更大的p，只需使用--p而不是++p。正如迈克尔建议的那样，无论你喜欢这个还是重复二进制搜索，都取决于数组的大小和你期望的重复次数。现在，您的问题标题是指自定义比较函数，但正如我所理解的那样，这里无法帮助您的问题 - 比较函数必须将任意两个等效对象比较为等效，因此无法识别几个等效对象中的哪一个是数组中其类型的第一个/最后一个。除非你有不同的问题，特别是有关比较功能的问题？

春驹晴陪

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