使用迭代器进行二分搜索

使用迭代器进行二分搜索是迭代器运算的一个经典案例之一，二分搜索是指在给定的 有序序列 中查找某个想要的元素的过程：

首先给出二分搜索的查找范围，然后通过计算得到所给范围中的中间位置元素的值，如果这个中间元素的值与所要查找的元素值相等，则搜索成功，程序完成，否则，比较这个中间元素的值与所要搜索的值的大小，倘若所要搜索的值大于这个中间元素的值，则所要搜索的值应该在这个有序序列的后半部分，此时，改变二分搜索所给范围的起始位置，重新计算新范围中间位置的元素所对应的值，倘若所要搜索的值小于这个中间元素的值，则所要搜索的值应该在这个有序序列的前半部分，此时，改变二分搜索所给范围的终止位置，重新计算新范围中间位置的元素所对应的值，重复以上过程，直至找到我们想要找到的元素或者没有元素可供继续搜索为止。

举个例子，如果所给的有序序列为：

3， 5， 6， 8， 11， 24， 33

第一种情况，所给的有序序列中有我们搜索的元素，譬如我们要搜索的元素是 24 ，这个有序序列共有 7 个元素，如果这 7 个元素存储在数组中，则它们在数组中的位置分别为 0, 1, 2 ... 6，二分搜索的查找范围为 0, 1, 2 ... 6，首先找出中间元素的位置 0 + (6 - 0)/2 = 3，则中间元素为 8，而 24 > 8，故所要搜索的元素在这个有序序列的后半部分，改变所给查找范围的起始位置为 3 + 1 = 4，得到新范围中中间元素的位置为 4 + (6 - 4)/2 = 5，则中间元素为 24，与我们要搜索的元素的值相等，搜索完成；

第二种情况，所给有序序列中没有我们要搜索的元素，譬如我们要搜索 7， 7 < 8，在这个有序序列的前半部分，所给范围的终止位置发生改变，终止位置变为 3 - 1 = 2，新范围的中间元素的位置为 0 + (2 - 0)/2 = 1，中间元素的值为 5， 7 > 5，若所给序列存在元素 7则应该在这个序列的后半部分，刚才所得新范围的起始位置应发生改变，起始位置变为 1 + 1 = 2，再次得到的新范围的中间元素的位置为 2 + (2 - 2)/2 = 2，即中间元素为 6，6 < 7, 但是新范围的起始位置，中间位置与终止位置相同，则这个序列中已经没有可以搜索的元素，结束搜索。

为了帮助理解使用迭代器进行二分搜索的算法思想，上面以文字的形式描述了在数组中存入有序序列时二分搜索的具体实现过程，下面来看看使用迭代器进行二分搜索的具体实现代码：（假设这个有序序列被存储在名为 text 的 vector 对象中）

auto beg = text.begin(), auto end = text.end();  // 二分搜索的最初查找范围
auto mid = text.begin() + (end - beg)/2;    // 中间元素的迭代器
// 当所给序列中有元素尚未检查并且还没有找到我们搜索的值 sought 时执行循环
while (mid != end && *mid != sought) {
    if (sought < *mid)   // 所搜索的值在序列的前半部分
        end = mid;
    else                 // 所搜索的值在序列的后半部分
        beg = mid + 1;
    mid = beg + (end - beg)/2;   // 计算新范围中间元素的位置
}

注意区别，数组中的终止位置确实关联一个实际存在的元素，但是迭代器 end 返回的总是序列中最后一个元素的下一个位置，即尾后元素，要特别加深理解 while 语句中的代码：

mid != end