Рекурсивный бинарный поиск в php

Question

У меня есть функция, которая дает мне число в результате:

Теперь, чтобы сделать это проще, я буду использовать придуманный пример:

   function generate($a) {return $a*2;}
   //this is just an example, the real generate function is really expensive in terms of speed and resources

У меня также есть массив сзначения для передачи в эту функцию:

$array = array(1,3,4,6,8,9,11);

Я бы хотел найти значение $ array, которое, переданное в generate (), выдает в качестве выходного числа ближайшее к 5 и меньшее из него.

При прогрессивном поиске я получу это:

$array[0] => 2;
$array[1] => 6;
$array[2] => 8;
etc.

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

Поскольку функция generate () очень медленная (в среднем 1,5 секунды), я хочу выполнить двоичный поиск снадежда на сокращение использования моей функции.

В общем, я хочу сделать следующее: разрезать массив $ на две части, использовать generate (), затем разрезать еще и т. д.

Я не эксперт по рекурсивным функциям и бинарному поиску (это мой первый скрипт, пытающийся это сделать).

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

<code>function generate($a) {return $a*2;}

$array = array(1,2,3,4,5,6,7,8,9);

function find($array) {
    $first_half = array_slice($array,0,round(count($array)/2,0));
    $second_half = array_slice($array,round(count($array)/2,0));
    echo "<pre>";
    print_r($first_half);
    print_r($second_half);
    echo "

"; $ last = end ($ first_half); $ last = generate ($ last); if ($ last> 4) {find ($first_half);} else {}} find ($ array);

Вы можете мне помочь?

С уважением, Джорджио

Answer 1

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

То, что вы хотели бы, это оптимизировать generate() (или как это называется*), а не алгоритм обхода.

---

* Одним из таких улучшений является замена этого:

foreach($array as $k=>$v) $array[$k] = generate($v);

на это:

$array = array_map('generate', $array);

Answer 2

Для бинарного поиска вот что вы хотите сделать:

• Если в списке, в котором вы ищете, есть только один элемент, то верните этот элемент в качестве ответа.
• В противном случае найдите элемент, ближайший к середине (если в списке есть четное количество элементов, он не будет идеальным, просто округлите его вниз).
• Рассчитайте для этого значение generate()средний элемент:
  • Если результат равен 5 (или любому другому значению, которое вы ищете), тогда верните этот средний элемент в качестве ответа.
  • Если результат больше пяти, рекурсивно вызовитеfind() со списком всех элементов, которые были до середины, и возвращаем это.
  • Если результат меньше пяти, рекурсивно вызовите find() со списком всех элементов, которые идут после середины,и верни это.