% java BinarySearch 1.txt < 2.txt
2 つのテキスト ファイル (1.txt と 2.txt) があり、2.txt には 1.txt にない値が含まれている場合、これらの値を得るためにバイナリ検索はどのように機能しますか? への引数BinarySearch
がキーとソートされた配列である場合、これがどのように適用されるかわかりません。
二分探索のコードは次のとおりです。
import java.util.Arrays;
public class BinarySearch {
// precondition: array a[] is sorted
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public static void main(String[] args) {
int[] whitelist = In.readInts(args[0]);
Arrays.sort(whitelist);
// read key; print if not in whitelist
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if (rank(key, whitelist) == -1)
StdOut.println(key);
}
}
}
ウィキペディアによると、私が理解したことから、バイナリ検索または半間隔検索アルゴリズムは、ソートされた配列内の指定された値 (入力「キー」) の位置を見つけます。
では、2 つのテキスト ファイルで珍しい値を見つけるにはどうすればよいのでしょうか。