c++ primer Binary Search 通过迭代器

Question

问题在评论里!

代码:

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

这个问题困扰了我很长时间。

Answer 1

一个更简短的答案:

不变的是 end 始终是要搜索的区间的“结束点”。

由于您要搜索的区间是 beg .. mid-1，因此 mid 是“最后一个”迭代器。