我在下面的教科书中读到一个问题,其中说 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;
最佳答案
课本说的对;这个问题是一个理论问题,即使尝试多种实现也无法帮助您伪造声明(您最多只能找到一个证明声明的实现)。
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 的比较运算符,程序就会崩溃严格弱排序)。
关于c++ - 在 {8, 4, 6, 2} 中搜索 4 时,是否有任何 std::binary_search 的实现会返回 true?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46988597/