C++意外行爲的binary_search

以下片段返回給我0.我預計它是1.這裏發生了什麼問題？C++意外行爲的binary_search

#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

來源

2013-07-11 David

二分查找是否需要排序數組？ 'v'排序？ – andre

你可以發佈代碼的輸出嗎？你從「cout」陳述中得到什麼？ – wlyles

我跑的程序，並看到了這個：

11 
22 
10 
20 
30 
40 
50 

Binary Search - 0

你的陣列沒有排序，因此二進制搜索失敗。（它看到11在第一個位置，並且10的結尾在此不存在）

您要麼確保在二進制搜索之前對數組進行排序或使用常規std::find。

來源

2013-07-11 21:08:43 milleniumbug

這是答案。你不能二分搜索一個未排序的數組。 –

binary_search說：如果

檢查排序範圍[first, last)包含等於 value的元件。第一個版本使用operator<來比較元素，第二個版本使用給定的比較函數comp。

您的列表不排序，它包含的元素11和之前1022。

來源

2013-07-11 21:09:58

您的數組未被排序，所以binary_search有未定義的行爲。嘗試std::find代替

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

§的C++ 11標準（3242草案）25.4.3.4

要求：所述的元件E [第一，最後一個）相對於分割表達式e <值和！（值爲<e）或comp（e，值）和！comp（值，e）。此外，對於[first，last）的所有元素e， e < value implies！（值<e）或comp（e，value）意味着！comp（值， e）。

來源

2013-07-11 21:10:26 RiaD

「意外的行爲」？這裏沒有什麼意外的。

二分查找算法的整體思想是利用輸入數組爲排序的這一事實。如果數組未被排序，則不能進行任何二進制搜索。

當您使用std::binary_search（以及所有其他標準的基於二分搜索的算法）時，輸入序列必須按照與std::binary_search所使用的謂詞相同的比較謂詞進行排序。由於您未將任何自定義謂詞傳遞給std::binary_search，因此它將使用由<運算符定義的順序。這意味着您輸入的整數序列必須按升序排序。

在你的情況下，輸入序列不滿足該要求。 std::binary_search不能用於它。

來源

2013-07-11 21:21:55 AnT

C++意外行爲的binary_search

回答

相關問題