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中的递归三元搜索：将数组分为三部分，并递归搜索给定元素

回答

相关问题