0

我正在尝试创建一个不使用数组的二进制搜索。它还需要计算在找到数字之前它进行了多少次搜索。我还必须使用随机访问文件。

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

用户输入您要搜索的号码。我需要在不使用扫描仪类的情况下执行此操作。这样做的方法将非常有帮助

我知道这就是您使用数组进行二进制搜索的方式。我需要帮助弄清楚如何在没有数组的情况下做到这一点

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

这实际上不是一个特定于 java 的问题，而是一个算法问题。虽然没有说明，但您的 binarySearch 显然是基于文件以某种方式神奇地排序。

也就是说，您知道 raf.writeInt(xxx) 会将规范化的字节长度值写入文件。将文件本身视为一个数组，其中每个索引位置为 a[i * 4] == 因此，创建将“mid”、“low”和“high”计算为所需索引的倍数的小函数。

谷歌“外部排序”

于 2013-04-18T18:46:17.707 回答
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 回答