使用迭代器進行二進制搜索

問題出在評論中。使用迭代器進行二進制搜索

#include <iostream> 
#include <vector> 
using namespace std; 
int main() 
{ 
    vector<int> ivec = {15,17,19,25,45,78,98}; 
    auto beg = ivec.begin() , end = ivec.end(); 
    auto mid = beg + (end-beg)/2; 
    int sought; 
    cin>>sought; 
    while(mid != end && *mid !=sought) //why not "mid != beg"? 
    { 
     if(*mid>sought) 
      end = mid; 
     if(*mid<sought) 
      beg = mid + 1; 
     mid = beg + (end-beg)/2; 
    } 
    if(*mid == sought) 
     cout<<"Found"; 
    else 
     cout<<"Not Found"; 
}

根據C++ Primer 5th Edition，在這一段時間結束時，mid將等於end，否則它將表示我們正在查找的元素。如果mid等於end，那麼元素不在文本中。

我用end替換beg後運行程序，它運行得很好。

來源

2017-08-24 Toy_Soldier

如果我發佈一個更好的實現作爲一個答案，它是脫離主題嗎？這段代碼有許多功能，使我能夠（我意識到代碼來自一本書）。 –

這是這本書的代碼嗎？這對我來說似乎不正確 - 它會導致UB。 – Slava

@NirFridman如果你這樣做會很有幫助。 –

爲什麼不「mid！= beg」？

因爲它修復後會破壞這個程序，目前它已經壞了。所以，首先你得讓它正確的，因爲你的代碼違揹你說的話：

在同時結束，中期將等於結束，或將表示爲此我們正在尋找

元素

所以最後一個條件必須是：

if(mid != end) 
    cout<<"Found"; 
else 
    cout<<"Not Found";

否則，當你在你的例子進入sought> 98，你會得到UB。

現在在修復程序後，如果在while循環條件中將mid != end更換爲mid != beg，則算法將中斷 - 例如對於一個元素矢量，它總是會說「找到」。

來源

2017-08-24 22:05:07 Slava

end，過去的結束迭代器，表示一個無效元素，因此它不能被解除引用。您必須首先確認mid不是end，因此您可以比較指出的值。

您的版本可能會調用未定義的行爲，並且如果搜索到的元素是第一個，則該行爲將不起作用。

來源

2017-08-24 21:26:46 erenon

即使這個版本可以有UB - ''mid'在引用前不會被檢查爲有效 – Slava

使用迭代器進行二進制搜索

回答

相關問題