2分探索と線形探索

Question

public class Member {
public int id;
public String name;

public Member(int id, String name) { 
    this.id = id;        
    this.name = name; 
} 

public static Member findMemberById(int id, Member[] data) {

}
public static Member findMemberByName(String name, Member[] data){

} 

}

Member [] dataはメインクラスで定義して、会員番号順にデータを格納しました。ここから会員番号をキーにして 2 分探索 で会員を探し出すメソッド「fMI」と、会員名をキーにして線形探索で会員を探し出すメソッドを作成したいのですが、やり方がよくわかりません。後発見できなかった時はnullを返すようにしたいです。

Answer 1

二分探索を行うユーティリティーメソッドがArraysクラスにあるのですが、おしいことにインターフェースがちょっとばかり柔軟さを欠いているために本件の検索に自然には使えません。少し工夫すると使えなくはないのですがあまりほめられた実装ではないと思うので、自前で二分探索を実装したほうが好ましいと思います。

二分探索はyubaさんの回答がアルゴリズムとしては美しいと思いますが、末尾再帰になることから(それを人間が置き換えたとしてもそれほどわかりにくくはないので)単純ループで実装してもよいと思います。コンパイラーが末尾再帰を最適化してくれると分かっている場合はあえて再帰のままにしておくのがよいかも知れませんが。(Javaコンパイラーは末尾再帰を最適化してくれるのでしたっけ・・・？)

public static Member findMemberById(int id, Member[] data) {
  int minIndex = 0;
  int maxIndex = data.length;
  while (minIndex < maxIndex) {
    int index = (minIndex + maxIndex) / 2;
    Member m = data[index];
    if (id < m.id) {
      max = index;
    } else if (id > m.id) {
      min = index + 1;
    } else {
      return m;
    }
  }
  return null;
}

なお、名前での探索は線形探索とのことですが、性能ネックになる可能性があるならHashMapを検討というのがよくあるパターンですのそれも覚えておくとよいと思います。

Comments

[yuba]

二分探索ならTreeMapもありましたね。そっちの発想をするのを忘れていました。

javaは末尾再帰の最適化してくれないです。

[swordone]

間違えた。問題なかった。

[KSwordOfHaste]

二分探索は初歩的なアルゴリズムではありますが境界条件のプログラミングによい教材だとは思います。無限ループになるかどうか、なるとしたらどう対処するか閲覧者の方々それぞれで考えてみていただきたいと思います。プログラミングに慣れている方にとっても(少なくとも)頭の体操になりますし、初学者の方々にもアルゴリズムを考える練習になると思います。
ちなみにminIndex<maxIndexの条件があるのですが無限ループになりますか？

Answer 2

本当なら丸投げ案件なので書きたくなかったんですが…

private static Member findMemberById(int id, Member[]data, int left, int right) {
  // 左右が逆になってしまったら、見つからなかった
  if (left > right) return null;

  // 中央 こう書かないと、(あまりないだろうが)オーバーフローが発生してしまうとのこと。
  int pivot = left + (right - left) / 2;

  if (data[pivot].id == id) return data[pivot];
  // 範囲中央のidが探索対象idより小さい場合、小さい側(左半分)に可能性はない
  else if (data[pivot].id < id) return findMemberById(id, data, pivot + 1, right);
  // 範囲中央のidが探索対象idより大きい場合、大きい側(右半分)に可能性はない
  else return findMemberById(id, data, left, pivot - 1);
}

線形探索に関しては、配列の先頭から順番に名前を探せばいいです。
ってかこれくらいググればすぐ出て来る。

Answer 3

private static Member findMemberById(int id, Member[]data, int left, int right)
{
  // 略
}

というちょっと引数の余計にあるメソッドを作るところから始めます。
left, rightとは何か。
data配列のどこからどこまでを探すかという範囲です。left以上right未満の範囲で調べるということ。
すると、最初のfindMemberByIdの中身はこうなります。

public static Member findMemberById(int id, Member[] data) {
  return findMemberById(id, data, 0, data.length);
} 

そしたら、最初に書いた引数の多いやつの中身をどうするか。
二分探索だから、自分自身を利用します。

private static Member findMemberById(int id, Member[]data, int left, int right)
{
  // 幅がゼロなら、見つからなかった
  if (left == right) return null;

  // 中央
  int pivot = (left + right) / 2;

  if (data[pivot].id == id) return data[pivot];
  if (data[pivot].id > id) return findMemberById(id, data, pivot + 1, right);
  return findMemberById(id, data, left, pivot);
}

これが二分探索です。

Comments

[swordone]

これだと、leftとrightの幅が1になった際に抜けられなくなり、オーバーフローします(pivotが以降leftの値から変われなくなるため)。
該当しないことがわかったpivotが範囲に入らないようにしなければいけません。

[yuba]

ぎゃ。

[yuba]

終端条件を追加しました。

[yuba]

いや、終端条件を追加しなくても、右側の再帰を findMemberById(id, data, pivot + 1, right); と記述すればクリアできますか。

[swordone]

というか、それが本来の二分探索ですから。
そもそも不一致確定のpivotの位置まで範囲に入れる必要がないのです。

[swordone]

しかも自分の回答書いてて気づいたのですが、大小関係の判定逆です。

[yuba]

うわ、ほんとだ逆…

[A-pZ]

ありがちです (・ω|