使用遞歸方法進行三元搜索

Question

我在寫一個遞歸方法，它不是執行二分搜索算法，而是將數組拆分爲三個並使用三元搜索算法。我相當肯定我遞歸的情況是正確的，但是我的基本情況似乎有問題。如果數組包含兩個或更少的值，則基本情況應該是非遞歸檢查，如果該值在數組中並返回索引。如果未找到該值，則返回-1。

由於我無法弄清楚的原因，無論如何這個方法返回-1。無論數組的大小，還是數組是否包含該值。這是方法。

public static int trinarySearch(int[] array, int x, int low, int high) { 

    if (high - low < 3) { //BASE CASE. 
     for (int i = low; i < high; i++) { 
      if (array[i] == x) { 
       return i; 
      } 
     } 
     return -1; 
    } else { //RECURSIVE CASE. 

     int firstThird = low + (high - low)/3; 
     int secondThird = low + 2 * (high - low)/3; 

     if (x <= array[firstThird]) { 
      return trinarySearch(array, x, low, firstThird - 1); 
     } else if (x <= array[secondThird]) { 
      return trinarySearch(array, x, firstThird + 1, secondThird - 1); 
     } else { // must be (x > array[secondThird]) 
      return trinarySearch(array, x, secondThird + 1, high); 
     } 
    } 
} 

在我的測試代碼，我只是建立一個數組作爲INT []數組= {1，2，...}

比方說，我搜索INT 2，它在數組中。我在測試代碼中設置了一個數組，並將該方法調用爲trinarySearch（array，2，0，array.length-1）。它每次打印-1。該方法有什麼問題，或者我只是簡單地設置了我的測試代碼？

Answer 1

您好像在混合您的邏輯low和high。通常情況下，您可以定義檢查中的子數組，從low（含）開始，並以high（不含）爲結束。

您使用high包容性（因爲我使用array.length-1您的示例調用理解），但隨後循環像

for (int i = low; i < high; i++) { 

不參觀array[high]。

快速修復是將<更改爲<=並且您的代碼運行良好。不過，我會建議使用標準清晰度（High獨家），因爲它也簡化了代碼的其他部分：

• 你不需要任何的錯誤傾向+1或-1指數修正（不要忘了在您的遞歸情況下將<=更改爲<）。
• high-low正在檢查子數組的大小，所以你可以使用high-low <= 3這更清楚地表明你的基本情況處理陣列的最大長度是3

Answer 2

我想你不明白Heuster答案。以下是我會做，它在我看來，Heuster說的話一樣：

public static int trinarySearch(int[] array, int x, int low, int high) { 

     if (high - low < 3) { //BASE CASE. 
      for (int i = low; i < high; i++) { 
       if (array[i] == x) { 
        return i; 
       } 
      } 
      return -1; 
     } else { //RECURSIVE CASE. 
      int firstThird = low + (high - low)/3; 
      int secondThird = low + 2 * (high - low)/3; 

      if (x < array[firstThird]) { 
       return trinarySearch(array, x, low, firstThird); 
      } else if (x < array[secondThird]) { 
       return trinarySearch(array, x, firstThird, secondThird); 
      } else { // must be (x > array[secondThird]) 
       return trinarySearch(array, x, secondThird, high); 
      } 
     } 
    } 

Answer 3

你只是錯過了一個重要的條件在遞歸截面爲if(x==splitingIndex)

我不得不改變你的代碼一點點及其工作
看到的變化

public static int trinarySearch(int[] array, int x, int low, int high) { 

    if (high - low < 3) { 
     //BASE CASE. 
     for (int i = low; i < high; i++) { 
      if (array[i] == x) { 
       return i; 
      } 
     } 
     return -1; 
    } else { //RECURSIVE CASE. 

     int firstThird = low + (high - low)/3; 
     int secondThird = low + 2 * (high - low)/3; 

     if(x == array[firstThird]) 
     { 
      return firstThird; 
     } 
     else if (x < array[firstThird]) { 
      return trinarySearch(array, x, low, firstThird - 1); 
     } 

     if(x == array[secondThird]) 
     { 
      return secondThird; 
     } 
     else if (x < array[secondThird]) { 
      return trinarySearch(array, x, firstThird + 1, secondThird - 1); 
     } 



      return trinarySearch(array, x, secondThird + 1, high); 
     } 
    }