Java中文件中遞歸二進制搜索中的StackOverflowError

Question

filepointer卡住導致StackOverflowError的一個點。你能指出我在這裏有什麼錯誤嗎？錯誤的確切是：java.lang.StackOverflowError

我正在尋找找到的位置，因爲記錄寬度不固定。

這裏是一段代碼：

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

這應該是mreal + 1.

此外，遞歸對二進制搜索來說是過度的......通常循環更快。

羅爾夫

編輯：====

OK，所以它仍然無法正常工作。這是因爲我只是部分正確。我只看了一下代碼並看到了問題，但後來我用錯誤的值修復了它。

除了添加1之外，還應添加字符串中與您比較的字符數加上行終止符（如果有的話 - 可能是最後一行...）。

這整件事告訴我的是這可能是家庭作業......以及遞歸練習和二分搜索研究。

沒有爲你做功課，我會花一點時間批評你的代碼。

二進制搜索應該找到中點，然後，如果中點匹配，則返回它，如果它大於搜索，則在中點之前搜索，否則在中點之後搜索。

您的代碼正在獲得中間點「正確」和「之前」的權利，但它沒有在'之後搜索......因爲您沒有計算'之後'部分的權利..您需要成爲'在'整個字符串之後，而不是在第一個字符之後。修理它。請記住，使用readLine（）意味着你不知道行結束符（是'\ r \ n'還是'\ n'？）。我建議在「中間」點之後使用一個循環，然後自己向前走，直到找到另一個\ n，然後使用該（+1）來計算搜索後的位置，如果需要的話。

一些其他意見....

• 不要使用 '自動裝箱'。使用長基元而不是長對象。
• 爲什麼在變量'filepointer'中已知它返回的值時調用getFilePointer（）。
• 當計算「中間」，使用低+高>>> 1 ....它會打動你的講師，你可以說你知道爲什麼你讀這之後：http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html
• 當你正在閱讀的是，你可以找出爲什麼在循環中執行二進制搜索比在遞歸中執行二進制搜索更好。
• 如果你做使用遞歸，你應該把你的參數設置爲'final'，因爲這會在棧上留下更小的空間，你可以'更深'。
• 如果你做使用遞歸，那麼你應該儘量減少你在你的方法創建......像StringBuilders的對象....

羅爾夫

當你進入一個無限