c++ - 在 {8, 4, 6, 2} 中搜索 4 时，是否有任何 std::binary_search 的实现会返回 true？

Question

我在下面的教科书中读到一个问题，其中说 1 是一个可能的输出。我在 VS 和 g++ 中试过，都给出 0。课本错了吗？

int t[] = { 8, 4, 6, 2 };
deque<int> d1(t, t + 4);
cout << binary_search(d1.begin(), d1.end(), 4) << endl;

Answer 1

课本说的对；这个问题是一个理论问题，即使尝试多种实现也无法帮助您伪造声明(您最多只能找到一个证明声明的实现)。

binary_search 需要一个排序的数组，如果您传递一个未排序的数组，您将进入未定义的行为领域，在那里一切都可能发生，包括找到您的号码并返回 true。

例如，碰巧使用数组中的第二个位置作为第一个猜测的实现，或者切换到线性搜索短容器的实现可能很容易做到这一点。 hell ，即使是这样的东西也是一个完美符合的实现:

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value) {
    // check the first two values just because
    for(int i=0; i<2 && first != last; ++i, ++first) {
        if(!(*first<value) && !(value<*first)) return true;
    } 
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}

---

也就是说，更有趣的是，不仅 1 是可能的输出，而且 5 或 42 也是可能的，尽管 IMO 的可能性低于“段错误(核心转储)”；这就是说:未定义的行为真的是未定义的(而且我已经多次看到 libstdc++ std::sort 如果传递了一个没有定义 a 的比较运算符，程序就会崩溃严格弱排序)。