std::binary_search 没有按预期工作

Question

我尝试制作一个程序，使用 std::binary_search

检查数字是否在向量中

我知道我可以使用 std::find，但我听说 std::binary_search 比 std::find 快很多，所以我想在需要时学习使用它检查一个号码是否在容器中。

代码：

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::cout << "Enter number of elements: ";
    int n;
    std::cin >> n;
    std::vector<int> v(n);

    std::cout << "Enter the elements: ";
    std::for_each(v.begin(), v.end(), [](int &x)
    {
        std::cin >> x;
    });

    std::cout << "Enter a number: ";
    int number;
    std::cin >> number;

    bool doesItExist = std::binary_search(v.begin(), v.end(), number);

    if(doesItExist == false)
    {
        std::cout << "It doesn't exist!";
    }
    else std::cout << "It exists!";

    return 0;
}

我认为 std::binary_search 应该 return true 如果在容器中找到了数字。

现在我将用几个例子来解释我的代码发生了什么

在以下所有示例中，我将使用 10 个元素：

Enter number of elements: 10
Enter the elements: 1 10 100 -11 -112 -17 44 -99 99 558

1°

Enter a number: 1
It doesn't exist!

2°

Enter a number: 10
It doesn't exist!

它将一直这样，直到我输入最后两个数字之一（99 或 558）

前一个号码：

Enter a number: 99
It exists!

最后一个号码：

Enter a number: 558
It exists!

我不确定为什么会这样。如果有人能解释为什么会发生这种情况，为什么只有最后 2 个数字有效？什么是解决这个问题的方法？

谢谢

Answer 1

您误解了 binary search 的工作方式：您不能以任意顺序输入数字，并期望 binary_search 找到匹配项；范围内的项目必须订购。这是二分搜索在决定从中间、右边或左边走哪条路时所做的假设。

如果在读取数据后将此行添加到代码中，问题将得到解决：

std::sort(v.begin(), v.end());

此外，如果您按排序顺序输入数字，您的代码将无需修改即可运行：

-112 -99 -17 -11 1 10 44 99 100 558

Answer 2

通常对已排序的向量或数组应用二进制搜索

你的似乎没有排序。

对向量进行排序，然后重新检查结果。

std::binary_search 没有按预期工作

std::binary_search doesn't work as expected

algorithm

vector

binary-search