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，但我們應該這樣做...;）