StackruError в рекурсивном бинарном поиске в файле в Java

Question

filepointer застревает в точке, в результате чего StackruError, Можете ли вы указать мне, что именно здесь не так? Ошибка именно такова: java.lang.StackruError

Я пытаюсь найти местоположение, так как ширина записи не фиксирована.

Вот кусок кода:

private static void binarySearch(RandomAccessFile raf, String searchvalue, Long low, Long high) throws IOException
{
    Long middle = (low + high) / 2;
    Long mreal = null;
    if(low > raf.length() -1 || high > raf.length()-1 || low >= high) {
        System.out.println("Element not found:");   return ;
    }

    StringBuilder sb = new StringBuilder();
    for(long filePointer = middle; filePointer != -1; filePointer--) {
        raf.seek(filePointer);
        int readByte = raf.readByte();
        if(readByte == 0xA) {
            break;
        }

        sb.append((char)readByte);
    }

    String lastLine = sb.reverse().toString();
    System.out.println(lastLine);

    mreal = raf.getFilePointer();
    String str = raf.readLine();
    System.out.println(str);

    String values[] = str.split("\t",-1);
    int compared = searchvalue.compareTo(values[fieldindex]);
    System.out.println(fieldindex);

    if(compared == 0) {
        System.out.println("Value found. The other details:");
        for(int i=0; i < values.length;i++)
        System.out.print("\t" +  values[i]);
        return;
    } else if(compared < 0)
        binarySearch(raf,searchvalue,low,mreal-1);
    else if(compared > 0)
        binarySearch(raf,searchvalue,mreal,high);
}

Трассировки стека:

Исключение в потоке "основной" java.lang.StackruError

>at java.util.regex.Pattern$Node.<init>(Pattern.java:2993)
    >at java.util.regex.Pattern$CharProperty.<init>(Pattern.java:3332)
    >at java.util.regex.Pattern$CharProperty.<init>(Pattern.java:3332)
    >at java.util.regex.Pattern$BmpCharProperty.<init>(Pattern.java:3363)
    >at java.util.regex.Pattern$BmpCharProperty.<init>(Pattern.java:3363)
    >at java.util.regex.Pattern$Single.<init>(Pattern.java:3391)
    >at java.util.regex.Pattern.newSingle(Pattern.java:2951)
    >at java.util.regex.Pattern.atom(Pattern.java:1985)
    >at java.util.regex.Pattern.sequence(Pattern.java:1885)
    >at java.util.regex.Pattern.expr(Pattern.java:1752)
    >at java.util.regex.Pattern.compile(Pattern.java:1460)
    >at java.util.regex.Pattern.<init>(Pattern.java:1133)
    >at java.util.regex.Pattern.compile(Pattern.java:823)
    >at java.lang.String.split(String.java:2292)

Answer 1

else if(compared > 0)
    binarySearch(raf,searchvalue,mreal,high);

Это должно быть mreal + 1.

Кроме того, рекурсия избыточна для бинарного поиска.... обычно цикл быстрее.

Рольф

EDIT:====

ОК, так что все равно не работает. Это потому что я был только отчасти прав. Я только на мгновение посмотрел на код и увидел проблему, но потом исправил ее с неверным значением.

Вместо добавления 1, вы должны добавить количество символов в строке, с которой вы сравниваете, плюс конец строки (если есть - это может быть последняя строка...).

Все это говорит мне о том, что это, вероятно, домашнее задание... и упражнение по рекурсии и изучение бинарного поиска.

Не выполняя за вас домашнее задание, я проведу минуту, критикуя ваш код.

Предполагается, что бинарный поиск находит среднюю точку, а затем, если средняя точка совпадает, возвращает ее, если она больше, чем поиск, а затем выполняет поиск до средней точки, в противном случае выполняется поиск после средней точки.

Ваш код получает среднюю точку "правильно", а "до" - правильно, но он не ищет "после"... потому что вы не вычисляете "после" справа. Вы должны быть "после" целая строка, а не только после первого символа. Почини это. Помните, что использование readLine() означает, что вы не знаете терминатор строки (это '\r\n' или просто '\n'?). Я рекомендую использовать цикл после "средней" точки, а затем идти вперед, пока не дойдете до другого \ n, а затем использовать это (+1) для вычисления позиции поиска "после", если вам это нужно.

Некоторые другие комментарии....

• Не используйте "автобокс". Используйте длинные примитивы вместо длинных объектов.
• Зачем вызывать getFilePointer(), когда возвращаемое значение уже известно в переменной filepointer.
• При вычислении "среднего", используйте "низкий + высокий" >>> 1 ...., он поразит вашего лектора, и вы можете сказать, что знаете, почему, прочитав это: http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html
• Пока вы читаете это, вы можете понять, почему двоичный поиск в цикле лучше, чем в рекурсии.
• если вы используете рекурсию, вы должны установить свои параметры в 'final', потому что это оставляет меньшую площадь в стеке, и вы можете идти 'глубже'.
• если вы используете рекурсию, то вы должны минимизировать объекты, которые вы создаете в своем методе... как StringBuilders....

Рольф