使用遞歸只使用三個參數表在數組上進行二進制搜索

Question

所以基本上我嘗試構造一個遞歸函數來對已排序的數組執行二分搜索，儘管我很清楚在它後面流動的基本邏輯，但問題出現在我只需要傳遞三個參數給函數，它們是數組，它的大小和要搜索的項目。我知道我必須在數組的上半部分調用函數，如果該項位於數組的後一部分，反之亦然，但我該怎麼做？我在內部製作兩個新陣列，我該如何做到這一點？我很困惑

Answer 1

你甚至可以用2個參數來做。這裏是我的僞代碼：

find(array, item){ 
    //base case to return the item if found 
    if(array.length == 1 && array[0].equals(item)) { 
    return array[0]; 
    } 
    else { 
    return null; 
    } 

    //decide in which half to continue the search 
    if(array[array.length/2] >= item) { 
    return find(createSubArray(array, 0, array.length/2 -1); 
    } 
    else { 
    return find(createSubArray(array, array.length/2, array.length-1); 
    } 

    //never reached 
    return null; 
} 

這不會保護傳遞給方法的空數組或空值。

Answer 2

如果你在C/C++中這樣做的關鍵是要意識到數組作爲指針傳遞。因此，每次您遞歸調用函數時，都可以使用指針算術和明智選擇的大小指定數組的哪一部分。