二分探索について

Question

数値検索のアルゴリズムについて勉強していて、
現在二分探索について勉強しています。

二分探索の概要は理解できたのですが、
上手くソースコードに起こして実際に使うことができません。

どなたか簡単なサンプルを頂けないでしょうか。

Answer 1

Javaでサンプル作りました。
10万の配列からtarget変数の値を検索して比較回数を出力しています。
10万程度なら20回弱の比較で検索できますね。

ちなみにJavaだとArrays.binarySearchを使えば二分探索で検索してくれます。

`
public class BinarySearch {

// 検索値
private final int target = 12345;

// 検索対象データ
private final int[] datum = new int[100000];

public BinarySearch() {
    // 検索対象データ作成
    int length = this.datum.length;
    for(int i = 0;i < length;i++) {
        this.datum[i] = i;
    }

public static void main(String[] args) {
    // 検索
    BinarySearch bs = new BinarySearch();
    int result = bs.search(bs.target, 0, bs.datum.length, 1);
    System.out.println("result:" + result);
}

// 二分探索(min〜maxが検索対象範囲)
private int search(int target, int min, int max, int count) {

    // 中間の値の算出
    int half = (min + max) / 2;

    // 中間の値がminかmaxと一致したら存在しない判定
    if(half == min || half == max) {
        System.out.println("Data Not Found!!");
        return count;
    }

    int compared = this.datum[half];
    System.out.println(count + ":" + compared);

    // 一致したら比較回数を返して処理終了
    if(target == compared) {
        return count;

        // 一致しない場合に中間の値をmin・maxに設定し範囲を狭めて再度比較
    } else if(target < compared) {
        return this.search(target, min, half, ++count);
    } else {
        return this.search(target, half, max, ++count);
    }
}

}
`