Question

C++中使用迭代器完成二分搜索

auto beg = text.begin(), end = text.end();

auto mid = text.begin() + (end - beg) / 2;
while(mid != end && *mid != sought) { //这里为什么用mid!=end作为循环的条件
if(sought < *mid)

end = mid; //为什么这里不用end = mid -1这样搜索不是更快么？

else

beg = mid + 1;

mid = beg + (end - beg) / 2;

}

Answer 1

1）因为end是指向区间最后一个元素的后面（见下面2））；若找不到给定值，beg将移动到区间最后一个元素的后面（即end）,相当于常见的low>high(参考数据结构)；
2）因为迭代器text.end()是指向最后一个元素的后面，而不是最后一个元素，比如共有n个元素，则指向n+1;
所以在搜索完毕后，还要用代码判断是否搜索成功：
if(mid!=end)查找成功；
else 查找失败；

Answer 2

//这里为什么用mid!=end作为循环的条件

mid == end 的时候，begin==end，只有一个元素了。
//为什么这里不用end = mid -1这样搜索不是更快么？

end = mid-1；是更快但是注意这里mid的计算方式是：

mid = beg + (end - beg) / 2;

而不是mid = beg + (end - beg+1) / 2;所以end=mid-1是错误的。
比如0 1 2 3 4 搜索1.
第一次
beg = 0 end=4
mid=2
1<2
如果end =mid,又beg =0
则mid=0+（2-0）/2 = 1是正确的。
而如果end=mid-1，又beg=0
mid=0+（1-0）/2 = 0是错误的，找不到1.

Answer 3

可以是end = mid -1。

区别在于：

当元素个数为奇数个的时候，比如0，1，2，3，4，查找1。

end = mid -1的算法比end = mid 多一次while循环判断。

分析end = mid -1的情况：

初始beg指向0，end指向4后面的位置，此时mid指向2；

第一次循环：1<*mid，end = mid-1(end指向1)，计算mid(指向0)

第二次循环：1>*mid，beg = mid+1(beg指向1)，计算mid(指向1)

退出循环，此时*mid == 1，能够查找到。

分析end = mid 的情况：

初始beg指向0，end指向4后面的位置，此时mid指向2；

第一次循环：1<*mid，end = mid(end指向2)，计算mid(指向1)

退出循环，此时*mid == 1，查找成功。

Answer 4

有一点你搞错了
如果一个序列是 1，2，3，4
那么begin()指向1，end()是指向4后面一个位置，而不是4