爪哇 - 做一個二進制搜索遞歸

Question

所以幾個星期我一直在試圖來回創建以下代碼到一個遞歸方法...

public static int binarySearch(Comparable[] objArray,Comparable item) 
{  
    int lower=0; 
    int upper=objArray.length -1; 
    int i=-1; // if -1 is returned the search failed; 
    int compareResult; 
    boolean found= false; 
    while ((lower<=upper)&& (!found)) 
     { 
     i=(lower+upper)/2; 
     compareResult=item.compareTo(objArray[i]); 
     if (compareResult<0) 
      { 
      upper=i-1; 
      } 
     else 
      if (compareResult>0) 
       { 
       lower=i+1; 
       } 
     else 
      { 
       found=true; //item found in spot i 
      } 

     }// end of while 
     if (found==false) return -1; else return i; 

} 

我知道我必須重新定義了整數和使用幾個ifs，但沒有一個while循環我不明白如何得到我想要的最終遞歸代碼。有什麼建議麼？由於

-D

Answer 1

阻止你從看到遞歸的主要問題是你的方法的參數只是一個數組和比較器。如果你要傳遞開始和結束索引（通常在舊語言中做了什麼），你會看到遞歸的可能性。

我通常不喜歡給出這樣的問題的僞代碼，而寧願給你提示關於算法的結構和性質。但是，如果以這種方式定義方法，則無法將2 + 2放在一起。所以，我要在這裏做一個例外：

這不是（這是你所擁有的）：

public static int binarySearch(Comparable[] objArray,Comparable item) 
{  
    int lower=0; 
    int upper=objArray.length -1; 

你有這樣的（這是類似Java的僞代碼，高度簡化的，沒有錯誤檢查，你需要工作的實際語法細節）：

public static int binarySearch(Comparable[] objArray,Comparable item) 
{  
    return bSearch(objArray, item, 0, objArray.length -1); 
    .... 

private static int bSearch(Comparable[] objArray,Comparable item, int lower, int upper) 
{ 
    if(lower > upper /* not found */){ return -1; }; 

    int pivot = ((int)((upper - lower)/2)) + lower; 

    int cmp = objArray[pivot].compareTo(item); 

    if(cmp == 0){ return pivot; } 
    else if (cmp < 0){ return bSearch(objArray,item, lower, pivot - 1); } 
    else{ return bSearch(objArray,item, pivot+1, upper); } 
} 

同樣，你需要的工作比實際的語法和參數的驗證，但另一方面，這是一個遞歸二進制搜索典型的僞代碼。您應該已經看到了這一點，並最近在大二的編程課程中對它進行了惡作劇。

遞歸發生在：

1. 如果你的數組進行排序，並

2. 如果你開始在中間的比較，又名樞軸，

3. 和比較失敗，

4. 然後

5. 你知道你只需要搜索一半（上半部分如果目標>樞軸或下半部分，如果目標<樞軸）。

所以，你拿，你要尋找的，並再次執行就可以了完全相同的步驟一半。除了調用完全相同的算法以外，還有什麼更好的方法可以實現，只有那部分輸入的子集才具有完全相同的功能？

這是遞歸。

---

編輯：在前面的例子闡述，當你想/需要執行遞歸在Java中的東西，最好是有一個功利方法，它採用的數據結構作爲一個整體（說只是陣列和比較對象，就像你在例子中所做的那樣）。

然後調用一個內部方法，實際遞歸（並且必須處理參數傳遞）。原因是您的調用者不必傳遞較低和較高的索引（因爲它們可以從數組對象中計算出來）。

在其他較低級別的語言（如C，Pascal或Ada）中，您有時無法計算這些參數，必須用調用者明確傳遞的參數聲明遞歸函數。

ergo爲什麼我在上面的僞代碼中單獨的bSearch函數中分割遞歸。

Answer 2

那麼，考慮如何你可能會改乘......你進行一個對比，你縮小了搜索範圍，對不對？所以你需要在遞歸方法的參數中指出。

嘗試傳入當前已知的下限和上限作爲參數，而不是while循環 - 並將您的while條件測試更改爲初始測試以查看是否已完成。

Answer 3

想象一下：

你得到一個較小的陣列基於一些條件進行搜索。但是你的函數的目的也是在數組中尋找一個元素。所以，不要自己來處理它，而是讓新的調用來處理它。你只是擔心回報價值。如果它是-1，則知道該元素現在已找到，並且返回-1。如果其他任何事情都返回，則返回它，因爲它是找到的元素的索引。

Answer 4

如果您已經理解了遞歸，請跳過此操作。

遞歸性是這樣的：

• 你有一個（或多個）基本條件（S）。這些將用於知道何時停止。

• 您有輸入參數。一個（或許多）這個輸入參數將用於停止條件。

• 你有一些運做，並通過與新參數調用相同的功能（因爲使用相同的將永遠遞歸），該操作將被「解決」

因此，與此記信息，你可以做這樣的事僞：

boolean contains(element , list) { 
    //Q. what is the base condition? 
    //A. to know if there are elements in the list right? 

    if list.isEmpty()? return false; // not found in an empty list 

    // Q. What other base condition we may try? 
    // A. If the list contains only one element, we may see 
    // if it is our element. 
    if list.size() == 1 
     return list.firstElement() == element // true if they are false otherwise 

    // Finally we may try as base condition to test 
    // if our element is in the middle of the list 
    if list.middleElement() == element ? return true // we found it 


    // Ok, none of our base contidion worked. 
    // Now we have to perform some operation 
    // Here's the recursion magic: 
    // Solve your problem by invoking this same function (re-course it) 
    // with different arguments. In this sample, we 
    // split the original list in two. 

    return contains(element , list.firstHalf()) 
      or contains(element , list.secondHalf()) 

    // you may read it as: 
    // "this list contains element if it is in the first half or it is in the second half 
} 

通過在兩個分裂的列表中，搜索將縮小到列表中的每個包含一個元素，或者是空的一個點。當發生這種情況時，我們的基礎條件將會停止遞歸。如您所見，如果您首先確定基本條件，然後確定如何修改參數，則會更容易。

在嘗試在代碼中執行此操作之前，首先嚐試使用僞代碼或鉛筆和紙張進行此操作非常重要。正如您在我的示例中看到的，我調用了輔助方法（firstElement(), middleElement(), firstHalf(), secondHalf()），因爲它們與問題無關。您必須首先了解如何解決問題，然後轉到具體的語言問題。

我希望這可以幫助你更好地理解遞歸。

如果你還沒有嘗試this link

Answer 5

您需要了解稱爲"Divide and Conquer"遞歸的特定技術。

基本上，如果您可以將問題分爲兩個較小的相同問題，那麼您可以輕鬆應用遞歸，前提是您的部門最終將問題簡化爲易於解決的問題。

在這種情況下，您正在查找數組以查找項目。分而治之的解決方案將如下所示：

1. 如果我有一個排序數組，我可以將我要查找的項目與該數組中的中間元素進行比較。如果它不匹配，我選擇對應於我想要查看的方向（更高或更低）的較小陣列，然後重複該過程。
2. 如果我有一個大小爲1的數組，那麼我只需要將該項與我正在查找的項進行比較，如果它不在那裏，那麼該數組不存在於該數組中。
3. 如果我有一個大小爲零的數組，那麼我正在查找的元素不存在於該數組中。

應始終首先檢查退出條件。這可以防止在不合適的情況下進行遞歸，並保證每次遞歸評估時都會確保在停止時適當停止。

boolean exists(Comparable[] X, Comparable item) { 

    if (X.length == 0) return false; 
    if (X.length == 1) return (X[0].compareTo(item) == 0); 
    int pivot = X.length/2; // integer math assures an integer result 
    if (X[pivot].compareTo(item) == 0) return true; 
    if (X[pivot].compareTo(item) < 0) { 
    Compareable[] right = new Comparable[X.length-pivot-1]; 
    System.arrayCopy(X, pivot+1, right, 0, right.length); 
    return exists(right, item); 
    } else { 
    Compareable[] left = new Comparable[X.length-pivot-1]; 
    System.arrayCopy(X, 0, left, 0, left.length); 
    return exists(left, item); 
    } 

} 

它是僞代碼，並沒有優化，但它應該讓你想到你需要的方式。嘗試一些自己創建的問題的技術;因爲這是一個非常重要的概念，所以你不想僅僅根據分配的作業問題（或兩個）來理解。你需要對這個想法有一個很好的理解;它將在學校和工作中再次看到。