1

以下代码段返回 0。我希望它是 1。这里出了什么问题？

#include <iostream>
#include <iterator>
#include <ostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
  vector<int> v;
  int arr[] = {10,20,30,40,50};
  v.push_back(11);
  v.push_back(22);
  copy(arr,arr + sizeof(arr)/sizeof(arr[0]),back_inserter(v));  // back_inserter makes space starting from the end of vector v
  for(auto i = v.begin(); i != v.end(); ++i){
    cout << *i << endl;
  }
  cout << endl << "Binary Search -  "  << binary_search(v.begin(), v.end(), 10) <<endl; // returns bool 
}

我正在使用 gcc /usr/lib/gcc/i686-linux-gnu/4.6/lto-wrapper

4

4 回答 4

13

我运行程序并看到了这个：

11
22
10
20
30
40
50

Binary Search -  0

您的数组未排序，因此二进制搜索失败。（它11在第一个位置看到，并且10在这里得出结论不存在）

您要么希望确保在二进制搜索之前对数组进行排序，要么使用常规的std::find.

于 2013-07-11T21:08:43.837 回答
4

“意外行为”？这里没有什么出乎意料的。

二分搜索算法的整个想法是利用输入数组已排序的事实。如果数组未排序，则不能对其进行任何二进制搜索。

当您使用std::binary_search（以及所有其他标准的基于二分搜索的算法）时，输入序列必须按照与所使用的比较谓词相同的比较谓词进行排序std::binary_search。由于您没有将任何自定义谓词传递给std::binary_search，因此它将使用<运算符定义的顺序。这意味着您的输入整数序列必须按升序排序。

在您的情况下，输入序列不满足该要求。std::binary_search不能用在上面。

于 2013-07-11T21:21:55.303 回答
4

binary_search说：

检查排序范围是否[first, last)包含等于 的元素 value。第一个版本用于operator<比较元素，第二个版本使用给定的比较函数comp。

您的列表未排序，它包含元素11和22之前的10.

于 2013-07-11T21:09:58.437 回答
4

你的数组没有排序，所以binary_search有未定义的行为。试试std::find吧

bool found = std::find(v.begin(), v.end(), 10) != v.end()

C++11 标准第 25.4.3.4 节（3242 草案）

  1. 要求：[first,last) 中的元素 e 根据表达式 e < value 和 !(value < e) 或 comp(e, value) 和 !comp(value, e) 进行分区。此外，对于 [first, last) 的所有元素 e，e < value 意味着 !(value < e) 或 comp(e, value) 意味着 !comp(value, e)。
于 2013-07-11T21:10:26.180 回答