Форум PHP

Имеется массив диапазонов:

<?php  $diap_array[1] = array( 1,5 );  $diap_array[2] = array( 5,6 );  $diap_array[3] = array( 8,10 ); ?>

Каким образом получить номер диапазона, в который входит, к примеру $val = 3 ?

Пользовательской функцией сравнения или в цикле.

В цикле - это долго. А если диапазонов 10 тыс от 11111111111 до 99999999999 и определить номера диапазонов нужно для 10 тыс чисел?

А про пользовательскую функцию сравнения - подробней плз, что вы имеете в виду?

А как вы хотите без цикла? Даже используя готовые функции, вы все равно будете использовать цикл, правда за вас это сделает РНР. Вот применяя такие функции, типа array_walk, вы "в теневом режиме" и обойдете массив циклом, указывая свою функцию сравнения элементов массива.

Хочу что-то типа бинарного поиска, но только для двойных диапазонов. Но не могу придумать, как его к этой задаче применить.
Неужели нет элегантного решения?..

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

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

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

Не в начале, а в середине.
Все же это быстрее, чем array_walk. В некоторых случаях в сотни раз.

цикл --> array_sum()/2 <= 3?

Вот так бы это вяглядело в C для массива a(1...n);

int first = 0; // Первый элемент в массиве   int last = n; // Последний элемент в массиве     if ( x < a[first] || x > a[last] ) {     // x лежит вне заданного массива   }     while ( first < last ) {     int mid = ( first + last ) / 2;  // В Си это эквивалентно целочисленному делению на 2 в   // других языках (дробная часть отсекается)     if ( x <= a[mid] ) {       last = mid;     } else {       first = mid + 1;     }   }     if ( a[last] == x ) {     // Искомый элемент найден. last - искомый индекс   } else {     // Искомый элемент не найден. Но если Вам вдруг надо     // его вставить со сдвигом, то его место - last.   }

И что по вашему, в этом нет обращений к элементам массива? И это не деление массива на 2, как вы выразились.

Да почитайте вы уже википедию, чтоли..
Обращения есть, но массив делится для сокращения числа проходов.
http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA

Я вижу деление суммы значений элементов на 2, а не массива.

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

К слову сказать, не представляю, чем бы помог array_walk. для поиска позиции.
arrray_map еще хоть как-то можно прицепить. И там array_sum рак раз к месту.

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

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

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

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

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

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

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

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

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

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

Не понял.

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

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

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

<? $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]);

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

Википедию пишут не особо одаренные люди. А с sim5 я бы спорить не стал!

А почему это? ) Мой ник еще не означает, что я всегда прав ;-)

Довольно самокритичное и верное утверждение, хотя бы в контексте этого треда.

Ну и зря.

элегантным было бы как раз сформировать одномерный массив границ отрезков,
пройтись по нему дихотомией либо до конца (получив ответ),
либо до уменьшения диапазона поиска до приемлемых границ (после чего применить встроенные функции обхода)

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