使用二分查找错了吗？

Question

可能做错了什么？尝试使用二进制搜索从数组的 class 中删除一个实例。实例在创建时被添加到数组中，但是当我从场景中删除它们时，我希望它们也从数组中删除。不知何故 binary_search 在第一次删除时工作正常，但在删除第二个实例时却不行。

如果在数组中找到实例，

binary_search 应该 return 为真。但它 return 是错误的，当实例肯定存在于数组中时。

这是我正在使用的代码。

void Manager::eraseInstance(SomeInstance* instance) {
    cout<< " found?: " << binary_search(instanceArray.begin(), instanceArray.end(), instance) << "  instance:  " << instance;
    for (int i = 0; i < instanceArray.size(); i++) {
        cout << "  " << i << ":  " << instanceArray[i];
    }
    cout << endl;
    if (binary_search(instanceArray.begin(), instanceArray.end(), instance)) {
        for (int i = 0; i < instanceArray.size(); i++) {
            if (instanceArray[i] == instance) {
                instanceArray.erase(instanceArray.begin() + (i));
                delete instance;
            }
        }
    }
}

为了调试，我首先计算搜索结果，然后是我尝试删除的实例，然后是数组中存在的所有实例。

现在我在控制台中的输出如下：

正在删除第一个实例输出：

found?: 1 instance: 05DCB358 0: 05DCAED8 1: 05DCB358 2: 05DCADB8

好的所以那里一切顺利，找到了实例，实例标识符与数组中的第二个实例相同。一切正常。

正在删除第二个实例输出：

found?: 0 instance: 05DCADB8 0: 05DCAED8 1: 05DCADB8

因此，我尝试删除的下一个实例发生了这种情况。二分查找找不到实例（但如您所见，它仍然作为数组的第二个实例存在于数组中）。因为它 returns false 实例没有被删除，即使我的输出确认实例存在，但 binary_search 说它不存在？

有人知道这里发生了什么吗？

Answer 1

binary_search 假设 collection 内容已经排序。

For std::binary_search to succeed, the range [first, last) must be at least partially ordered, i.e. it must satisfy all of the following requirements:

partitioned with respect to element < value or comp(element, value)

partitioned with respect to !(value < element) or !comp(value, element)

for all elements, if element < value or comp(element, value) is true then !(value < element) or !comp(value, element) is also true

由于您没有指定自定义比较逻辑，它将使用 operator< 来比较指针的数值。

因为你的collection内容是这样的：

0: 05DCAED8 1: 05DCB358 2: 05DCADB8

它们似乎没有排序（最后一个实际上具有最低值）所以 binary_search 失败。

使用二分查找错了吗？

Using binary search wrong?

c++

arrays

binary-search