Java中的遞歸三元搜索：將數組分爲三部分，並遞歸搜索給定元素

我試圖在給定元素的java數組中實現三元搜索。此時，我在數組的下三分之一處得到一個StackOverflowError，而在中間的三分之一處得到不正確的結果。非常感謝。Java中的遞歸三元搜索：將數組分爲三部分，並遞歸搜索給定元素

public class TernarySearch { 

    static int[] ints = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    public static int search(int[] a, int x, int low, int high) { 
    // int mid = (high + low)/2; 
    int thirdile = a.length/3; 
// System.out.println(a.length/3); 
// System.out.println(thirdile); 

    if (low > high) { 
     System.out.println("low is greater than high. Item not found."); 
     return 0; 

    } else if (x > a[(high-(thirdile - 1))]) { // upper third 
     System.out.println("X is greater than mid. higher third."); 
     return search(a, x, (high - thirdile), high); 
    } else if (x > a[thirdile - 1] && x < (high -thirdile)) { // middle third 
     System.out.println("X is in the middle third."); 
     return search(a, x, thirdile + 1, (high - thirdile) - 1); 

    } else if (x < a[thirdile -1 ]) { // lower third 
     System.out.println("X is less than thirdile. lower third."); 
     return search(a, x, low, thirdile); 
    } 
    else { 
     System.out.println("Found it at first thirdile"); 
     return thirdile; 
    } 

} 

public static void main(String[] args) { 

    System.out.println(search(ints, 2, 0, ints.length - 1)); 
}

}

來源

2011-11-29 user1070619

這個'&& X <（高-thirdile）'似乎沒有必要 – MeBigFatGuy

我要段搜索到三三（你會與兩半），所以它的意思劃分中間陣列的第三部分。沒有它，搜索會跨越陣列的三分之二。 – user1070619

好像你不能減少/增加正確的邊界。例如，你第一次調用前三分之一時，你正在檢查x是否大於位於高位（thirdile - 1）的索引值爲6的值。但是，你傳遞的索引值爲5，當你應該通過價值7爲低。這可能導致永遠不會孤立頂級三分之一的價值......我想在低位和中位有一個類似的錯誤。

來源

2011-11-29 06:13:34

謝謝。我通過了低位（高位）的指數，即7位，而不是5位。該值被正確隔離。遞歸只是永遠不會結束，導致StackOverflow。 – user1070619

好吧，所以我知道這個問題是舊的。但我想我會爲未來的人們提供一個答案，他們正在研究這個問題。你的代碼與terile做一些奇怪的事情。也在你的if語句並不全是包容性的。你錯過了不同的-1或者當你不應該時-1。同樣在遞歸調用中，您並不總是將低或高設置爲應該設置的值。希望這個代碼將有助於人走出

public class TernarySearch { 
    static int[] ints = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

    public static int search(int[] a, int key, int low, int high) { 
     // int mid = (high + low)/2; 
     //int thirdile = (high + low)/3 
     int firstThird = ((high+1)-low)/3; 
     int secondThird = ((2*((high+1)-1))/3); 
     // System.out.println(a.length/3); 
     // System.out.println(thirdile); 

     if (low > high) { 
      System.out.println("low is greater than high."+ key +" not found."); 
      return -1; 

     } else if (key > a[secondThird]) { // upper third 
      System.out.println("key is greater than secondThird. its in higher third."); 
      return search(a, key, secondThird+1, high); 
     } else if (key > a[firstThird]) { // middle third 
      System.out.println("key is in the middle third."); 
      return search(a, key, firstThird+1, secondThird); 
      // high is secondThird, because it could be equal to the secondThird still 
      // all we know is that it wasn't higher than a[secondThird], but was higher 
      //than a[firstThird] 
     } else if (key < a[firstThird]) { // lower third 
      System.out.println("key is less than thirdile. lower third."); 
      return search(a, key, low, firstThird-1); 
     } 
     else { 
      System.out.println("Found it at first third at index: "+firstThird); 
      return firstThird; 
     } 

    } 

    public static void main(String[] args) { 

     System.out.println(search(ints, 2, 0, ints.length - 1));//print out the index number that is returned 
     //if it is -1 that is printed out, 2 wasn't found, else it was found 
     int myKeyIndex = search(ints, 2, 0, ints.length-1); 
     if(myKeyIndex != -1) 
      System.out.println(ints[myKeyIndex]+ "was found in the array!!"); 
     else 
      System.out.println("Didn't find the key!!"); 
    } 

}

來源

2014-04-03 02:52:10 user3491950

Java中的遞歸三元搜索：將數組分爲三部分，並遞歸搜索給定元素

回答

相關問題