(Java) 类似于二进制的搜索，但使用 /3 而不是 /2

Question

我创建了一个程序来比较不同的搜索方法，这些搜索方法从 0-999 的排序数组中搜索随机 int 值 0-999。我创建了一个完美运行的二进制搜索，在执行此操作之后我决定尝试创建一个搜索，而不是将值分成两半，而是将它们分成 1/3 和 2/3，具体取决于。所以基本上如果我有 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} 我正在寻找 10 我会从上面到 {6,7,8,9,10,11,12,13,14,15} 至 {10,11,12,13,14,15} 至 {10,11} 然后简单的 {10} 和 return 这个值的索引。

我目前有：

int loopTotal3 = 0;
    for(int y = 0; y < 1000; y++){
        System.out.println("Reference1");
        int first = 0;
        int last = array0Through999.length - 1;
        int third = (array0Through999[0] + array0Through999[999]) / 3;

        int findThis3 = rand.nextInt(1000);
        int loop3 = 0;
        while(first <= last){
            System.out.println("Reference2");
            loop3++;
             if (array0Through999[third] < findThis3){
                 System.out.println("Reference3");
                 first = third + 1;
             }
             else if(array0Through999[third] ==  findThis3){
                 System.out.println("Reference4");
                 break;
             }
             else{
                 System.out.println("Reference5");
                 last = third-1;
             }
             third = (first + last) / 3;
        }
        loopTotal3 = loopTotal3 + loop3;
    }
    int loopAverage3 = loopTotal3 / 1000;
    System.out.println("The average number of times for a Binary Search is: " + loopAverage3 + "\n");

代码目前在第一个 if 语句中卡住运行，我不确定原因。

关于我的问题有什么想法或者这个逻辑是否接近正确？

Answer 1

在较小的数据集上使用相同的算法，我发现了一个问题。使用只有 3 个成员的数组：0 1 2。尝试找到 2。第三个将卡在 1 上，并且永远不会上升到足够高以找到 2。

这将无限循环，永远不会达到 2。您可能在代码的其他地方遇到了类似的 window。因为它进入了第一个 if，所以它执行 first = third + 1 产生 first = 2. third=(first+last)/3=4/3=1.

Answer 2

import java.util.Random;

public class weqfgtqertg {
    public static void main(String args[]) {
        int array0Through999[] = {0,1,...,999};
        int loopTotal3 = 0;
        Random rand = new Random();
        for(int y = 0; y < 1000; y++){
            //System.out.println("Reference1");
            System.out.println(y);
            int first = 0;
            int last = array0Through999.length - 1;
            int third = (first + last) / 3;

            int findThis3 = rand.nextInt(1000);
            int loop3 = 0;
            while(first <= last) {
                //System.out.println("Reference1");
                loop3++;
                 if (array0Through999[third] < findThis3){
                     //System.out.println("Reference3");
                     first = third+1;
                 }
                 else if(array0Through999[third] ==  findThis3){
                     //System.out.println("Reference4");
                     break;
                 }
                 else{
                     //System.out.println("Reference5");
                     last = third-1;
                 }
                 int calc = last - first;
                 third = first + (calc/3);
            }//end while
            loopTotal3 = loopTotal3 + loop3;
        }//end for
        int loopAverage3 = loopTotal3 / 1000;
        System.out.println("The average number of times for a Tertiary Search is: " + loopAverage3);
    }
}

我发布这个问题已经有一段时间了，但我终于开始解决我的问题了。这是任何可能偶然发现此代码的人的正确代码。

编辑：该数组包含“...”以使其在阅读或显示在屏幕上时不会令人讨厌。我的数组中的所有 0-999 都被硬编码了。

(Java) 类似于二进制的搜索，但使用 /3 而不是 /2

(Java) A search similar to Binary but using /3 instead of /2

java

arrays

search

binary-search

sortedlist