配列またはリストに並べられたデータがソートされている場合には、本2分探索法を使うと探索時間を大幅に減らすことができる。それは、データ全体を2つのグループに分けて、探すキーがどのグループに属しているかを判定し、属している部分を更に2つの小さなグループに分けて繰り返して調べていく方法だから。

<関数名>
  binarySearch 2分探索

<形式>
  int binarySearch(DATA *data, int nmem, int target);

<引数>
  typedef struct {
    int key;   /* 比較のキーとなるフィールド */
    int info;  /* その他のフィールド */
  } DATA;

  data   (入力) データレコードの配列
  nmem  (入力) レコード配列の大きさ
  target  (入力) 探索目標とするキーの値

<関数値>
  見つかった場合は配列の要素番号(配列の先頭要素の番号は0)。見つからなかった場合は -1。

注意事項
  データレコードのキーデータが昇順に正しくソートされていることが前提条件である。

用例

<関数本体>
  binarySearch.c

<説明>
  1回の比較で探索すべき範囲は半分になるので、探索成功あるいは失敗のどちらの場合でも、計算量は O(log n) 。
  データが降順でソートされている場合は、不等号の向きを変ればよい。

Comments are closed.

Post Navigation