無法理解C++ STL中的1行代碼源：Lower_Bound/Upper_Bound

Question

我正在編寫一些代碼來查找其值不超過PHP給定整數的最後一個鍵。例如，數組（0 => 1,1 => 2,2 => 3,3 => 3,4 => 4）。給定整數3，我會找到密鑰3.（二進制搜索）

而且我查找了一些關於Internet上二進制搜索的參考。
我覺得這是爲了找到第一個鍵值不小於給定C++整數的鍵。
它說：

template <class _ForwardIter, class _Tp, class _Distance> 
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, 
          const _Tp& __val, _Distance*) 
{ 
    _Distance __len = 0; 
    distance(__first, __last, __len); 
    _Distance __half; 
    _ForwardIter __middle; 

    while (__len > 0) { 
    __half = __len >> 1; 
    __middle = __first; 
    advance(__middle, __half); 
    if (*__middle < __val) { 
     __first = __middle; 
     ++__first; 
     __len = __len - __half - 1; 
    } 
    else 
     __len = __half;  // <======this line 
    } 
    return __first; 
} 

那麼，爲什麼用 「__len = __half;」而不是「__len = __half + 1;」？
在這個二進制搜索過程中，「_middle」在每個循環中引用的鍵/值是否會被遺忘並丟失？
我的意思是，它似乎是兩個「__len」的不會加起來滿‘__len’，似乎__middle已跳過

PS： 我對我原來的問題PHP代碼爲：

$cid_start = $count - 1; 
$len  = $count; 
while($len > 0){ 
    $half = $len >> 1; 
    $middle = $cid_start - $half; 
    if($c_index[$middle][1] > $time_start){ 
     $cid_start = $middle - 1; 
     $len  = len  - $half - 1; 
    }else{ 
     $len  = $half + 1; 
    } 
} 

它會工作嗎？或者它會錯？
當我在數組中找不到任何東西時，如何獲得-1或其他值作爲結果？

Answer 1

只是回答「爲什麼不......」？問題：這個算法有些不同。如果下界實際上是第一個元素，我們會遇到問題。

__len將被減半了，直到它的2：

while (__len > 0) 
{ 
    __half = __len >> 1; // __half is __len/2 floored 

    __middle = __first + __half; // Assuming random access iterators, simplified 

    if (*__middle < __val) // Lower bound is __first, so *__middle >= __val 
    { 
     // […] 
    } 
    else 
     __len = __half + 1; // .. self-explanatory 
} 

，然後我們得到了一個無限循環。即，當__len == 2：

while (__len > 0) // Okay, 2 > 0 
{ 
    __half = __len >> 1; // __half is now 2 >> 1, which is 1 

    __middle = __first + __half; // Rewritten for clarity. __middle == __first. 

    if (*__middle < __val) // lower bound is at __first, so *__middle >= __val 
    { 
     // […] 
    } 
    else 
     __len = __half + 1; // __len is 1 + 1 == 2 
} // Endless loop 

如果指定的長度爲__half本身就無法這樣做 - 那麼對於__len == 2我們得到1，和__len == 1我們得到0

Answer 2

二進制搜索算法非常簡單。

/** 
* Search $value in $array 
* Return the position in $array when found, -1 when not found 
* $array has numeric consecutive keys (0..count($array)-1) 
* $array is sorted ascending; this condition is mandatory for binary search 
* if $array is not sorted => the output is rubbish 
*/ 
function search($value, array $array) 
{ 
    // At each step search between positions $start and $end (including both) 
    $start = 0; 
    $end = count($array) - 1; 

    // End when the search interval shrunk to nothing 
    while ($start <= $end) { 
     // Get the middle of the interval 
     // This is shorter and faster than intval(($start + $end)/2) 
     $middle = ($start + $end) >> 1; 

     // Check the value in the middle of the current search interval 
     if ($value == $array[$middle]) { 
      // Found 
      return $middle; 
     } 

     // Not found yet; the binary step: choose a direction 
     if ($value < $array[$middle]) { 
      // Search in the left half 
      $end = $middle - 1; 
     } else { 
      // Search in the right half 
      $start = $middle + 1; 
     } 
    } 

    // Not found 
    return -1; 
}