遞歸二進制搜索

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()並返回中間後面的所有元素的列表。