目次> 第11章> 11.7 TOPUPPREVNEXT

11.7 オブジェクトの配列と探索

名前と電話番号の配列を作成し、名前(よみ)で順次探索をし電話番号を表示してみましょう。

プログラム SeqSearch2.java

実行結果

 SeqSearch2-1.gif

 SeqSearch2-2.gif

 SeqSearch2-3.gif

 SeqSearch2-4.gif


データ件数が少ない場合は先頭から順に探せばいいのですが、データ件数が多い場合は、効率が問題となります。 データを小さい順に並べておけば、2分探索というアルゴリズムが使えます。

2分探索 (にぶんたんさく) binary search のアルゴリズム

簡単にいうと、順に並んでいるデータの中央に位置するデータを調べれば、前半分をにあるか後半分にあるかが判明するので、 これを繰り返して探す方法です。 つぎのようなステップになります。
  1. 探す先頭位置を s 番目、 最後の位置を e 番目とする
  2. s>e であれば、「探しているデータは無い」。(計算終わり)
  3. s==e であれば、このデータと探すデータを比較し、
  4. 等しければこのデータが探しているデータ、(計算終わり)
  5. 等しくなければ「探しているデータは無い」。(計算終わり)
  6. (s + e) / 2 番目のデータの値を m とする
  7. 探すデータ と m を比較する
  8. 等しければ、このデータが探しているデータ。(計算終わり)
  9. 探すデータが m より小さければ、 探す最後の位置を (s + e)/2 - 1 にして、2.に戻る。
  10. 探すデータが m より大きければ、 探す先頭位置を (s + e)/2 + 1 にして、2.に戻る。

小さい順にならべかえる(整列する)ことについては、13章で説明します。いろいろな方法がありますが、 ここでは、オブジェクトの大小を比較できるように インタフェース Comparable を実装( CompareTo メソッドを定義 ) しておき、 java.util.Arrays クラスの sort メソッドで オブジェクトの配列全体を整列するという方法を紹介します。

Javaには、大小関係のあるデータを上手に蓄積したり、検索したりする仕組みがいろいろ用意されていて、 自分で検索プログラムを作成することはあまりありませんが、 ここでは、1回比較するたびに探す範囲を半分に絞り込んでゆくというアルゴリズムを理解してください。

プログラム SeqSearch.java との相違点:

プログラム BinarySearch.java

実行結果

 BinarySearch-5.gif

 BinarySearch-1.gif

 BinarySearch-2.gif      BinarySearch-3.gif

 BinarySearch-4.gif      BinarySearch-4.gif

 BinarySearch-4.gif

もとのデータの先頭と最後が検索できるかという確認の他に、 整列後に先頭になったデータと最後になったデータが整列できるかの確認を追加しました。
データの端についてきちんと動作確認をする習慣をつけましょう。

91行目の先頭の // を削って、ind の値をDOS画面に表示しています。 これにより、「いとう」と「わたなべ」が、整列後の先頭と最後であることの確認ができます。 確認が終わったら、またコメントに戻しておきましょう。 プログラムの他の部分を修正した場合、この確認を再度したくなることがよくあります。 物理的に削除しないことがコツです。


更新日:2005/08/03 TOPUPPREVNEXT