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

问题出在评论中。使用迭代器进行二进制搜索

#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

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

回答

相关问题