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