在 {8, 4, 6, 2} 中搜索 4 时，是否有任何 std::binary_search 的实现会 return 为真？

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.

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

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 的可能性低于 "Segmentation fault (core dumped)"；这就是说：未定义的行为是 really undefined（而且我已经多次看到 libstdc++ std::sort 如果传递了一个没有定义严格弱排序的比较运算符，程序就会崩溃).

在 {8, 4, 6, 2} 中搜索 4 时，是否有任何 std::binary_search 的实现会 return 为真？

Is there any implementation of std::binary_search will return true while search for 4 in {8, 4, 6, 2}?

c++

stl

binary-search