mercredi 1 juillet 2020

Loop condition works well with raw iterator but not with iterator deduction

In the snippet below, while(litr < = ritr) works well, but while(*litr < *ritr) can not be met and goes out of range and crashes when try to search element which is not present in vector. I understand, loop will work with raw iterators but Why loop condition can not be met with iterator deduction?

bool binarySearch(std::vector<int> sorted_list, int item)
{
    auto litr = sorted_list.begin();
    auto ritr = sorted_list.end()-1;

    while(litr <= ritr)
    {
        int leftindex = std::distance(sorted_list.begin(), litr);
        int rightindex = std::distance(sorted_list.begin(), ritr);

        int mid = (leftindex + ((rightindex-leftindex)/2));

        if(sorted_list.at(mid) == item)
        {
            return true;
        }

        if(item < sorted_list.at(mid))
        {
            ritr = sorted_list.begin() + mid-1;
        }
        else
        {
            litr = sorted_list.begin()+ mid+1;

        }
    }

    return false;
}

Aucun commentaire:

Enregistrer un commentaire