C++ primer二进制搜索迭代器

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是“一个过去结束”迭代器。

Answer 2

比方说，你想在搜索数字是一个数组，它们分别是：

11 26 33 68 87 99 

在循环的开始，start点11和end点，1号过去99和mid指向33。在循环的每次迭代中，end指向将在查找中使用的数字之后的1个数字。

假设您正在寻找26。如果您使用

end = mid - 1 

end将指向在第二次迭代26和26将永远不会被发现。

如果使用

end = mid 

end将指向在第二次迭代33和26最终会被发现。

Answer 3

让我们在一张纸上运行你的代码，看看这两种方法会发生什么;我将使用这个表示法：3.idx作为从输入中指向元素3的迭代器。

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

让我们来运行它：

Input: `12345`. 
Key: `-10`. 

beg = 1 
end = 5 
mid = 3 

3.idx != 5.idx and 3 not -10 
if(-10 < 3) 
    end.idx = 3.idx 
mid.idx = 1.idx + 1 = 2 

Now we check only "123": 

2.idx != 3.idx and 2 not -10 
if(-10 < 2) 
    end.idx = 2.idx 
mid.idx = 1.idx + 0 = 1 

Now we check only "12": 

1.idx != 2.idx and 1 not -10 
if(-10 < 1) 
    end.idx = 1.idx 
mid.idx = 1.idx + 0 = 1 

Now we check only "1": 

1.idx == 1.idx stop. 

与

现在：

auto beg = text.begin(), end = text.end(); 
auto mid = text.begin() + (end - beg)/2; 

while(mid != end && *mid != key) 
{ 

    if (key < *mid) 
     end = mid - 1 // Only change 
    else 
     beg = mid + 1; 
    mid = beg + (end - beg)/2; 
} 

，我们将得到：

Input: `12345`. 
Key: `-10`. 

beg = 1 
end = 5 
mid = 3 

3.idx != 5.idx and 3 not -10 
if(-10 < 3) 
    end.idx = 3.idx - 1 = 2.idx 
mid.idx = 1.idx + 0 = 1 

Now we check only "12": 

1.idx != 2.idx and 1 not -10 

STOP，你有没有看到发生了什么？

我们没有检查，如果2竟是key，但我们应该这样做...;）