C++——迭代器的运算

使用迭代器的经典算法是二分搜索。二分搜索从中间开始搜索，如果中间元素刚好是目标元素，搜索完成，如果不是，在前半部分或是后半部分继续搜索，重复二分搜索过程，直到找到目标元素：

迭代器下的二分搜索：

// text必须有序
// beg和end表示搜索范围
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end - beg)/2; // 初始状态下的中间点
// 当还有元素尚未检查并且我们还没找到目标元素时：
while (mid != end && *mid != sought) {
    if(sought < *mid)    // 目标元素在前半部分
        end = mid;       
    else                 // 目标元素在后半部分
        beg = mid + 1;
    mid = beg + (end - beg)/2;
}

该程序开始定义了三个迭代器，beg指向搜索范围内的第一个元素，end指向尾元素，mid指向中间元素。初始状态下，搜索范围是名为text的vector的全部范围。