StackOverflowError dans la recherche binaire récursive dans le fichier java

Question

Le filepointer est bloqué à un point résultant en un StackOverflowError. Pouvez-vous me montrer ce qui ne va pas ici? L'erreur est exactement: java.lang.StackOverflowError

Je cherche à trouver l'emplacement car la largeur d'enregistrement n'est pas fixée.

Voici le morceau de code:

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); 
} 

Trace de la pile:

Exception dans le thread "principal" java.lang.StackOverflowError

>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); 

Ce devrait être mreal + 1.

En outre, la récursivité est excessive pour la recherche binaire .... typiquement une boucle est plus rapide.

Rolf

EDIT: ====

OK, donc il ne fonctionne toujours pas. C'est parce que je n'avais que partiellement raison. J'ai seulement regardé le code pendant un moment et ai vu le problème, mais alors je l'ai fixé avec la valeur fausse. Au lieu d'ajouter 1, vous devez ajouter le nombre de caractères dans la chaîne que vous avez comparé, plus la fin de ligne (le cas échéant, il peut s'agir de la dernière ligne ...). Ce que tout cela me dit, c'est que c'est probablement des devoirs ... et un exercice de récursivité et une étude de recherche binaire. Sans faire le travail pour vous, je vais passer un moment à critiquer votre code.

La recherche binaire est supposée trouver le point médian, puis, si le point central correspond, la renvoyer, si elle est plus grande que la recherche, puis rechercher avant le point milieu, sinon rechercher le milieu.

Votre code obtient le point médian 'droit', et le 'avant' droit, mais il ne cherche pas 'après' ... car vous ne calculez pas la partie 'après' juste .. Vous devez être 'après' toute la chaîne, pas juste après le premier caractère. Répare le. Rappelez-vous, en utilisant readLine() signifie que vous ne connaissez pas le terminateur de ligne (est-ce '\ r \ n' ou juste '\ n'?). Je recommande d'utiliser une boucle après le point 'central', puis de marcher vers l'avant jusqu'à ce que vous arriviez à un autre \ n puis d'utiliser (+1) pour calculer la position de la recherche 'après' si vous en avez besoin.

D'autres commentaires ....

• Ne pas utiliser 'autoboxing'. Utilisez des primitives longues au lieu des objets Long.
• Pourquoi appeler getFilePointer() lorsque la valeur renvoyée est déjà connue dans la variable 'filepointer'.
• Lors du calcul du « milieu », utilisez bas + haut >>> 1 .... il impressionner votre professeur et vous pouvez dire que vous savez pourquoi après avoir lu ceci: http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html
• Pendant la lecture, vous peut comprendre pourquoi faire une recherche binaire dans une boucle est préférable que de le faire en récursivité.
• Si utilisez utilisez la récursivité, vous devriez définir vos paramètres sur 'final', car cela laisse un plus petit encombrement sur la pile, et vous pouvez aller plus loin.
• si vous faites récursion d'utilisation, vous devez réduire les objets que vous créez dans votre méthode ... comme StringBuilders ....

Rolf