Форум PHP

Ничего не стоит сократить число итераций в цикле, на число проверямых индексов (например, текущий и крайние от него, уже 3) умноженное на 2 (проверять индексы с обеих краев массива). Другими словами, проходить будем по массиву в конечном итоге не сколько циклом, сколько сдвигая указатель в нем. Но с каждым увелечинием такого сокращения итерации возврастает сложность кода, да и сам сдвиг указателя, это тоже задача. Это я к тому коду, что показывал.

Да, для поиска некоего числа, нашли некий оптимальный вариант. В задаче же нужно искать нечто иное, и подкручивать вышеуказаный вариант к ней... не считаю оптимальным решением. Хотя могут быть и суждения )

>Я ведь могу (как говорил выше) сократить итерации на произвольное число, но где та золотая середина, в который будет выигрыш от сокращения итераций и числом сдвигов в массиве, они ведь сами по себе и без затрат тоже не делаются.

Не понял.

Вот и я говорю, я лично не вижу выгоды. Дело даже не в том, что надо приготовить данные порядком идущие, а сам подход. Что так, что иначе, одинаково. Я ведь могу (как говорил выше) сократить итерации на произвольное число, но где та золотая середина, в который будет выигрыш от сокращения итераций и числом сдвигов в массиве, они ведь сами по себе и без затрат тоже не делаются.

>Так чего мы ищем - значения по краям массива?
Нет, конечно.
Мы определяем, в какой из отрезков попадает точка.
но для этого нужно найти ближайшую границу.

Мне представляется, что этот вид ((5, 6), (10, 18),(23, 35)) тоже не с неба упал, а построен по некоторому источнику данных.
И если для быстрого поиска разумно построить его по-другому (5,6,10,18,23,35), то так и следует поступить. Автор того же мнения (02.02.2011 в 19:12) .

Тут можно было бы посетовать что, мол, такой фокус пройдет только с упорядоченными и только с непересекающимися отрезками.
Но поиск в списке пересекающихся отрезков может давать неоднозначный результат, а это признак недопоставленной задачи.
Если отрезки не пересекаются, то получить упорядоченный список их границ проще всего опять же из источника данных. На худой конец - просто отсортировать.

Так чего мы ищем - значения по краям массива? А надо ведь иное, судя по вопросу. Раскладывать искусственно значения диапазона по краям, чтобы потом так обежать массив... что-то я не пойму выгоды.

вот последовательный поиск с просмотром всех элементов.
Путем прямого пересчета.
Быстрый на коротких массивах из-за встроенных функций.

<?  function idx_seq($needle, $haystack)  {     return array_sum(array_map(create_function('$t', 'return $t<'.$needle), $haystack)); }

вот стандартныхй дихотомический поиск, быстрый на длинных массивах из-за логарифмической сходимости

<?  function idx_dih($needle, $haystack)  {     $left = 0; $right = count($haystack);     do     {         $mid = ($left + $right) >> 1;         if($haystack[$mid] == $needle)           return $mid;         if($haystack[$mid] > $needle)             $right = $mid;         else             $left = $mid+1;     }while($left < $right)     return $mid; }

можно совместить одно с другим
На длинном массиве искать методом половинного деления до локализации в пределах некоторого числа элементов, а затем применить прямой пересчет.

Получится нечто вроде

<?  define ('HIGH_LIMIT', 1000 ); // константу придется подобрать.  function idx_dih($needle, $haystack)  {     $left = 0; $right = count($haystack);     do     {         $mid = ($left + $right) >> 1;         if($haystack[$mid] == $needle)           return $mid;         if($haystack[$mid] > $needle)             $right = $mid;         else             $left = $mid+1;     }while($left + HIGH_LIMIT < $right)     return $left + idx_seq($needle, array_slice($haystack, $left, $right-$left) ); }

если вернулось четное значение - отрезок найден.
Если нечетное - значит искомое лежит вне отрезков, и найдены соседние.
Возня с массивом со спаренными гранпицами здесь будет только мешать.

Думал, думал... ) При желании можно сократить число итераций до бессовестного, но ведь обходить придется все равно:

<? $a = array(   array(11,25),    array(5,6),    array(18,10),   array(61,25),   array(28,10),   array(1,4),   array(48,10) ); $n = 3; $c = count($a); for($i=0, $k=ceil($c/2); $i<$k; $i++) {   $m = array_sum($a[$i])/2 <= $n ? $i : array_sum($a[$c-($i+1)])/2 <= $n ? $c-($i+1) : null;   if($m) break; } print_r($a[$m]);

сократив число итераций вдвое. А проверяя и смежные индексы, втрое, и т.д. )

Да надо по большей части утром читать, тогда... ) Нет, array_walk просто упоминянул в свете вызова пользовательских функций.
Не понял, каким образом данное может помочь, искать то ведь надо то, что входит в диапазон крайних значений, а не значение. Другими словами, у автора есть сгруппированные конечные значения, и найти надо одно из пренадлежащих.

Спасибо, почему я сразу про одномерный не подумал. Премного благодарю.