Не могу понять 1 строку кода в C ++ STL Источник: Lower_Bound / Upper_Bound

Question

Не могу понять 1 строку кода в C ++ STL Источник: Lower_Bound / Upper_Bound

Я пишу некоторый код, чтобы найти последний ключ, значение которого не больше, чем данное целое число для PHP.
Например, массив (0 => 1,1 => 2,2 => 3,3 => 3,4 => 4). Учитывая целое число 3, я найду ключ 3. (Бинарный поиск)

И я искал ссылки на бинарный поиск в Интернете.
Я нахожу это, чтобы найти первый ключ, значение которого не меньше, чем данное целое число для 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 или что-то в результате, когда я ничего не нахожу в массиве?

1

binary-search c#lower-bound php stl

Решение

Другие решения

Просто чтобы ответить на вопрос «почему бы и нет …?» Вопрос: этот алгоритм работает немного иначе. Если нижняя граница на самом деле является первым элементом, у нас возникнет проблема.

__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.

0

Источник

Accepted Answer

Алгоритм бинарного поиска очень прост.

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

0