php - Can't Understand 1 Line of Code in C++ STL Source: Lower_Bound/Upper_Bound -

i writing code find last key value no more given integer php.
e.g.,array(0=>1,1=>2,2=>3,3=>3,4=>4). given integer 3, find key 3.(binary search)

and looked references binary search on internet.
find this, find first key value no less given integer c++.
says:

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

well, why using "__len = __half;" rather "__len = __half + 1;"?
won't key/value ,which "_middle" refers in each loop, forgotten , lost in binary-searching-process?
mean, seem 2 "__len"'s won't add full "__len", seems __middle has been skipped

ps: php code original question is:

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

will work? or err?
, how can -1 or result when find nothing in array?

the algorithm binary search simple.

/**  * search $value in $array  * return position in $array when found, -1 when not found  * $array has numeric consecutive keys (0..count($array)-1)  * $array sorted ascending; condition mandatory binary search  * if $array not sorted => output rubbish  */ function search($value, array $array) {     // @ each step search between positions $start , $end (including both)     $start = 0;     $end   = count($array) - 1;      // end when search interval shrunk nothing     while ($start <= $end) {         // middle of interval         // shorter , faster intval(($start + $end) / 2)         $middle = ($start + $end) >> 1;          // check value in middle of current search interval         if ($value == $array[$middle]) {             // found             return $middle;         }          // not found yet; binary step: choose direction         if ($value < $array[$middle]) {             // search in left half             $end = $middle - 1;         } else {             // search in right half             $start = $middle + 1;         }     }      // not found     return -1; }