jeudi 24 août 2017

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.

Aucun commentaire:

Enregistrer un commentaire