java - RandomAccessFile 的二分查找

Question

这是一种使用二分搜索在 RandomAccessFile 中搜索目标号码的方法。它专门处理整数。我已经完成了所有设置，但我得到了错误的数字。由于 raf 包含字节，而整数包含 4 个字节，因此我认为只需将高位减 4 并将低位加 4，其中在常规二分搜索中执行相同的操作为 1。显然情况并非如此，而且我很难理解一般的二进制 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...20raf.length 是 80(不是 20)，即 4* 20你有正确的路线，但需要按照 4 进行工作在这种情况下，您的高值是 79 而不是 76(使用上面的示例)那么高应该是长度 - 4

你可以尝试:low = 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;
            }