Бинарный поиск RandomAccessFile

Это метод, который ищет целевое число в RandomAccessFile, используя двоичный поиск. Он имеет дело исключительно с целыми числами. У меня все настроено, но я получаю неправильные цифры. Поскольку raf содержит байты, а целое число содержит четыре байта, я подумал, что просто уменьшу старший на 4 и увеличим младший на 4, тогда как те же операции выполнялись на 1 в обычном двоичном поиске. По-видимому, это не так, и мне трудно понять двоичный ввод-вывод в целом. Помощь?

//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

java search binary randomaccessfile
person PsylentKnight    schedule 03.12.2014    source источник
comment
Я рекомендую вам не делать этого. Создайте индекс. Я проводил эксперименты с бинарным поиском файлов несколько десятилетий назад. Вывод состоял в том, что именно поэтому у нас есть B-деревья.   -  person user207421    schedule 03.12.2014
comment
Это школьный проект, и это требования. В любом случае, я поиграл с ним еще немного, и он у меня работает, хотя я не до конца его понимаю.   -  person PsylentKnight    schedule 03.12.2014

Ответы (1)


arrow_upward
2
arrow_downward

int - 4 байта, поэтому скажем, что ваш файл содержит числа 1... 20. Длина raf.length равна 80 (не 20), т.е. 4 * 20. У вас есть правильные строки, но вам нужно работать с точки зрения 4 вашего высокого значения в в этом случае 79, а не 76 (используя пример выше), поэтому high должна быть длина - 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;
            }
person Kevin Hussey    schedule 03.12.2014
comment
Интересно, для второй строки у меня есть long high = (raf.length() - 4) / 4; И, похоже, сейчас работает. - person PsylentKnight; 03.12.2014