0

I'm trying to create a binary search that doesn't use an array. It also needs to count how many searches it does until it finds the number. I also have to use a randomaccessfile.

RandomAccessFile raf=new RandomAccessFile(new File("Project 10"),"rw");

//writing in random numbers. Different numbers will be used when it is being tested

raf.writeInt(-5);
raf.writeInt(-1);
raf.writeInt(122);
raf.writeInt(124);
raf.writeInt(125);
raf.writeInt(256);

user input what number do you want to search for. I need to do this without using the scanner class. the method to do this will be very helpful

I know this is how you do a binary search with an array. I need help figuring out how to do it without an array

public static int binarySearch(int[] list, int key) {
    int low = 0;
    int high = list.length - 1;

    while (high >= low) {
        int mid = (low + high) / 2;
        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;
    }
    return -low - 1; // Now high<low, key not found
}
4

3 に答える 3

1

ファイルを配列として扱う場合、配列やリストは必要ありません。ファイルがソートされていると仮定すると、擬似コードは次のようになります

  1. ファイル内の行数を取得します (推測する必要があるかもしれません...新しい行をカウントする方法がわからない)
  2. 総行数の 1/2 の値を読み取る
  3. 値が同じであれば完了です。小さい場合は、ファイルの前半を使用して繰り返します。大きい場合は、ファイルの後半で繰り返します。
于 2013-04-18T18:48:42.937 に答える
0 
Would something like this work?

public static int binarySearch(int raf//for the file?, int key//for input?){
int low=0;
int high=raf.length()-1
while (high>=low){
int mid=(low+high)/2;
if (key<raf.[mid])// Does the [] automatically make it an array
high=mid-1;
else if (key==raf.[mid])
return mid;
else
low=mid+1;
}
return-low-1//now high < low, key not found
}
}
于 2013-04-19T10:47:58.200 に答える