はじめMath! Javaでコンピュータ数学

第75回 計算量の数学 計算量と実際のコード その1

この記事を読むのに必要な時間:およそ 1 分

問題 バイナリサーチのプログラムを作りましょう。

前回の問題で作成したリニアサーチのコードを変更してバイナリサーチのコードを作成しましょう。最低限,クラス名が変わることと,execメソッドの挙動を変更することで対応できます。前回同様実行時間を計測し,リニアサーチの場合と比較してください。

解説

問題 バイナリサーチのプログラムを作りましょう。

以下にバイナリサーチのコードを示します。お手元の環境での実行時間を計測してみてください。

ソースコード:BinarySearch.java

01:public class BinarySearch {
02:
03:  public static int exec(int[] vals, int target) {
04:    int left = 0; /* start key of index */
05:    int right = vals.length - 1; /* end key of index */
06:    int mid; /* middle key of index */
07:    while(left <= right) {
08:      mid = (left + right) / 2; /* calc of middle key */
09:      if (vals[mid] == target) {
10:        return mid;
11:      } else if (vals[mid] < target) {
12:        left = mid + 1; /* adjustment of left(start) key */
13:      } else {
14:        right = mid - 1; /* adjustment of right(end) key */
15:      }
16:    }
17:    return -1;
18:  }// end of exec
19:
20:  public static void main(String[] args) {
21:    int len = 100000;
22:    int[] data;
23:    data = new int[len];
24:    for(int i=0; i<len; ++i) data[i]=i;
25:    int result;
26:    int repeat = 10000;
27:    long time;
28:    time = System.currentTimeMillis();
29:    for (int i=0; i<repeat; ++i){
30:      BinarySearch.exec(data,3);
31:      BinarySearch.exec(data,27);
32:      BinarySearch.exec(data,(int)(len/2));
33:      BinarySearch.exec(data,(int)(len*2));
34:    }
35:    time = System.currentTimeMillis() - time;
36:    System.out.println(time + "[msec]passed.");
37:  }// end of main
38:
39:
40:  private static void resultPrint(int result){
41:    if (result != -1) {
42:      System.out.println("[ Found ] index key = " + result);
43:    } else {
44:      System.out.println("[Not Found]");
45:    }
46:  }// end of resultPrint
47:
48:}// end of BinarySearch

以下はその実行結果です。

出力画面

C:\>java BinarySearch

16[msec]passed.

私の環境※3ではたったの16ミリ秒でした。0.016秒です。リニアサーチの約300倍早く終了しました!これって,すごい高速化ですね。リニアサーチなんて,使うべきじゃないね,と言ったっていいでしょう。

※3
CPU:Intel(R) Core(TM)2 Duo CPU U7500 1.06GHz,Memory 2GB,WinXP,java version ⁠1.6.0 12”

今回はここまで

次回は,バイナリサーチよりも小さい計算量の検索アルゴリズムを紹介します。そして実際のコードで試してみましょう。果たして,理屈通りに高速なのか?お楽しみに。

今回のまとめ

  • バイナリサーチの計算量を求め,プログラムを作成・実行しました。
  • バイナリサーチはリニアサーチよりも相当高速であることが分かりました。

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。