algorithm - 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应该返回 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