(Java) Поиск, аналогичный двоичному, но с использованием /3 вместо /2.

Я создал программу, которая сравнивает различные методы поиска, которые ищут случайное значение int 0-999 из отсортированного массива, который равен 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} и вернуть индекс этого ценность.

В настоящее время у меня есть:

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, и я не уверен, почему.

Любые идеи по поводу моей проблемы или если эта логика близка к правильной?


java arrays search binary-search sortedlist
person Michael Smith    schedule 17.11.2016    source источник
comment
int third = (array0Through999[0] + array0Through999[999]) / 3; переосмыслить это   -  person Naman    schedule 17.11.2016

Ответы (2)


arrow_upward
0
arrow_downward

Используя тот же алгоритм на меньшем наборе данных, я вижу проблему. Используйте массив только с 3 элементами: 0 1 2. Попробуйте найти 2. Третий застрянет на 1 и никогда не поднимется достаточно высоко, чтобы найти 2.

Это будет бесконечный цикл, никогда не получающий от третьего до 2. Возможно, вы попадаете в похожее окно где-то еще в коде. Поскольку он входит в первый if, он делает первый = третий + 1, что дает первый = 2. третий=(первый+последний)/3=4/3=1.

person Michael Greenblatt    schedule 17.11.2016
comment
Похоже, что это проблема сейчас, когда я смотрю на нее снова. Как только я сужу массив достаточно, я попытаюсь сделать что-то еще, чтобы просмотреть и найти его. Может быть, простой линейный поиск, если список постоянно сужается до достаточно малого размера. - person Michael Smith; 18.11.2016
comment
Теперь, когда вы видите, что приведенный выше комментарий был полезен, возможно, вы можете изменить его на +1 вместо -1 :-). - person Michael Greenblatt; 30.09.2017
comment
Решение ниже :) теперь работает как шарм. Хотя, как и ожидалось, он хуже бинарного поиска. - person Michael Smith; 02.10.2017

arrow_upward
0
arrow_downward 

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 в моем массиве.

person Michael Smith    schedule 24.04.2017