The question is in the comment!
Code:
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end - beg) / 2;
while(mid != end && *mid != key)
{
if (key < *mid)
end = mid; //why not end = mid - 1??
else
beg = mid + 1;
mid = beg + (end - beg) / 2;
}
This question have stuck me for a long time.
A much shorter answer:
The invariant is that end is always "one past the end" of the interval to search.
Since the interval you want to search is beg .. mid-1, mid is the "one past the end" iterator.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments