递归二进制搜索

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 

我也有一个数组的值，以传递给funcion：

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

我想找到$数组的值，即，通过产生（），给出了作为输出数最接近5和次要的它。

与逐行扫描的搜索，我会得到这样的：

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

在这种情况下，我希望我的搜索功能，得到输出作为本证的号码1值，传递到生成（），即送2作为输出，最接近的数量和未成年人5

由于产生（）函数是很慢（平均1.5秒）我想要做的是减少使用的希望二进制搜索我功能。

所以基本上我想要做的是：切片$阵列分为2块，用生成（），然后切片againg等

我不能同时在递归函数和二进制搜索专家（这是我的第一个脚本试图做到这一点）。

但是我试着写了一些我在下面粘贴的代码，但是它不起作用，并且我没有清楚的想法。

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 "</pre>"; 
    $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()，并列出所有在中间之前出现的元素，然后返回该结果。
  • 如果结果小于5，则递归调用find()并返回中间后面的所有元素的列表。