RandomAccessFile的二進制搜索

Question

這是一種使用二分搜索在RandomAccessFile中搜索目標編號的方法。它只涉及整數。我有每一個設置，但我得到錯誤的數字。由於一個raf包含字節，並且一個整數包含四個字節，所以我認爲我只需將高位遞減4，然後在普通的二進制搜索中將低位增加4即可。顯然情況並非如此，而且我一直在困難地考慮二進制I/O。幫幫我？

//determines if a target number is in a RandomAccessFile using a binary search 
//tracks the number of times it took to find that the number was/wasn't in the file 
public static void binarySearch(){ 
    Scanner input = new Scanner(System.in); 
    int target = 0; //the number being searched for 
    boolean targetFound = false; //indicates if the target is found 
    int searchCount = 0; //the number of times it took to find that the number was/wasn't in the file 

    System.out.print("Please enter the number you wish to search for: "); 

    target = input.nextInt(); 

    try{ 
     RandomAccessFile raf = new RandomAccessFile("Project10.dat", "r"); 
     long low = 0; 
     long high = raf.length() - 1; 
     int cur = 0; 

     while(high >= low){   
      long mid = (low + high)/2; 
      raf.seek(mid); 
      cur = raf.readInt(); 
      System.out.println(cur); //for debugging 

      searchCount++; 

      if(target < cur){ 
       high = mid - 4; 
      } 
      else if(target == cur){ 
       targetFound = true; 
       break; 
      } 
      else{ 
       low = mid + 4; 
      } 
     } 

     raf.close(); 
    } 
    catch(FileNotFoundException e){ 
     e.printStackTrace(); 
    } 
    catch (IOException e){ 
     e.printStackTrace(); 
    } 

    if(targetFound == true){ 
     System.out.println("The number " + target + " is in the file. It took " + searchCount + " tries to discover this."); 
    } 
    else{ 
     System.out.println("The number " + target + " is not in the file. It took " + searchCount + " tries to discover this."); 
    } 

}//end method binarySearch 

Answer 1

一個int是4個字節 所以說你的文件中包含數字1 ... 20 的的raf.length爲80（不是20），即4 * 20 你有正確的線路，但需要以4 工作你的高價值在這種情況下是79而不是76（使用上面的例子） 所以高應該是長度 - 4

你可以嘗試：低= 0;

long high = (raf.length()/4) - 1 // this is in terms of elements 

long mid = (low + high)/2 ... again element rather than where in byte array 

raf.seek(mid * 4) // You can use the *4 to access the correct location in bytes 
cur = raf.readInt() 
     if(target < cur){ 
       high = mid - 1; 
      } 
      else if(target == cur){ 
       targetFound = true; 
       break; 
      } 
      else{ 
       low = mid + 1; 
      }