探索とは多くのデータから望みのデータを見つけることをいう。多くの情報処理で用いられる基本操作の一つ。

線形探索は逐次探索、順探索ともいう。配列またはリストに並べられたデータを一つ一つ順に端から調べるだけの素朴な探索法だ。

<関数名>
  linearSearch 線形探索

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

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

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

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

用例

<関数本体>
  linearSearch.c

<説明>
 比較のループを回る回数は、探索が失敗の場合はn回、成功の場合は平均してn/2回。いずれにしても計算量は O(n)。

Comments are closed.

Post Navigation