🧩
【Java】２分探索
この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。
ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。
【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧
2分探索(binary search)
基本形
package chap03;
import java.util.Scanner;
public class BinarySearch {
//--- 配列aの先頭n個の要素からKeyと一致する要素を2分探索 ---//
static int binSearch(int[] a, int n, int key) {
int leftidx = 0; // 探索範囲先頭のインデックス
int rightidx = n - 1; // 探索範囲末尾のインデックス
do {
int centeridx = (leftidx + rightidx) / 2; // 中央要素のインデックス
if (a[centeridx] == key)
return centeridx;
else if (a[centeridx] < key)
leftidx = centeridx + 1;
else
rightidx = centeridx - 1;
} while (leftidx <= rightidx);
return -1;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
//--- 配列aの用意 ---//
System.out.print("要素数:");
int num = stdIn.nextInt();
int[] x = new int[num];
//--- 配列aに値を格納する ---//
System.out.println("昇順に入力してください。");
System.out.print("x[0];");
x[0] = stdIn.nextInt(); // 先頭要素を格納
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]:");
x[i] = stdIn.nextInt();
} while (x[i] < x[i - 1]); // 一つ前の要素より小さければ再入力
}
//--- 検索する要素を指定 ---//
System.out.print("探す値:");
int key = stdIn.nextInt();
//--- 探索前の時刻を取得 ---//
long startTime = System.currentTimeMillis();
//--- ２分探索実行 ---//
int idx = binSearch(x, num, key);
//--- 探索後の時刻を取得 ---//
long endTime = System.currentTimeMillis();
//--- 探索結果の表示 ---//
if (idx == -1)
System.out.println("その値の要素は存在しません。");
else
System.out.println("その値はx{" + idx + "]にあります。");
// 計測結果を表示
System.out.println("処理時間:" + (endTime - startTime) + "ms");
}
}
Arrays.binarySearchによる2分探索
java.util.Arraysクラスに所属するbinarySearchメソッドはあらゆる要素型の配列からの探索に対応できるように9種類が多重定義されている。今回はその中から自然な順序ではない並び方の配列からの探索を行うメソッドを用いた。
package chap03;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class PhysicalDataSearch {
//--- 身体データ ---//
static class PhysicalData {
private String name; // 氏名
private int height; // 身長
private double vision; // 視力
//--- コンストラクタ ---//
public PhysicalData(String name, int height, double vision) {
this.name = name;
this.height = height;
this.vision = vision;
}
//--- 文字列化 ---//
public String toString() {
return name + " " + height + " " + vision;
}
//--- 身長昇順用コンパレータを定義 ---//
private static class HeightOrderComparator implements Comparator<PhysicalData> {
public int compare(PhysicalData d1, PhysicalData d2) {
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
public static final Comparator<PhysicalData> HEIGHT_ORDER = new HeightOrderComparator();
}
//--- 配列の用意 ---//
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
PhysicalData[] x = {
new PhysicalData("Aさん", 162, 0.3),
new PhysicalData("Bさん", 168, 0.4),
new PhysicalData("Cさん", 169, 0.8),
new PhysicalData("Dさん", 171, 1.5),
new PhysicalData("Eさん", 173, 0.7),
new PhysicalData("Fさん", 174, 1.2),
new PhysicalData("Gさん", 175, 2.0),
};
//--- 探索する値を指定 ---//
System.out.print("何㎝の人を探しますか：");
int height = stdIn.nextInt();
//--- 探索前の時刻を取得 ---//
long startTime = System.currentTimeMillis();
//--- 探索の実行 ---//
int idx = Arrays.binarySearch(
x, // 配列xを探索する
new PhysicalData("", height, 0.0), // heigtをキーとして
PhysicalData.HEIGHT_ORDER // 探索手法はHEIGHT_ORDER
);
//--- 探索後の時刻を取得 ---//
long endTime = System.currentTimeMillis();
//--- 探索結果の表示 ---//
if (idx < 0)
System.out.println("その値の要素は存在しません。");
else {
System.out.println("その値はx[" + idx + "]にあります。");
System.out.println("データ：" + x[idx]);
}
// 計測結果を表示
System.out.println("処理時間:" + (endTime - startTime) + "ms");
}
}
学習内容まとめ
eclipse操作時に役立つショートカットまとめ
ご協力のほどよろしくお願いします。
Discussion