CODEWITHSUNDEEP
c++c++11vectoriterator
Toy_Soldier
Toy_Soldier

Reputation: 41

Binary search using iterator

The question is in the comment.

#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";
}

According to C++ Primer 5th Edition,at the end of the while, mid will be equal to end or it will denote the element for which we are looking. If mid equals end, then the element was not in text.

I ran the program after replacing end with beg and it runs just fine.

Upvotes: 1

Views: 2800

Answers (2)

Slava
Slava

Reputation: 44258

why not "mid != beg"?

Because it would break this program after it is fixed, currently it is already broken. So first you have to make it correct, as your code contradicts what you say:

at the end of the while, mid will be equal to end or it will denote the element for which we are looking

So last condition must be:

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

Otherwise you would get UB when you enter sought > 98 in your example.

Now after fixing your program if you replace mid != end to mid != beg in the while loop condition, your algorithm will break - for example it will always say "Found" for one element vector.

Upvotes: 1

erenon
erenon

Reputation: 19118

end, the past the end iterator, denotes an invalid element, thus it cannot be dereferenced. You have to first make sure mid is not end, so you can compare the pointed value.

Your version might invoke undefined behavior and would not work if the sought elem is the first.

Upvotes: 4

Related Questions