データの中から、あるデータを探すことを探索といいます。 ここでは二分探索 (アルゴリズムC 第2巻 p.8) を用いて探索を行います。
次のようなソートされたデータがある。
1 4 6 9 10 13 19 23 25 30
(1) このデータから二分探索を用いて 9
を探索する過程を書きなさい。
(2) このデータから内挿探索を用いて 9
を探索する過程を書きなさい。
二分探索、内挿探索はソートされているデータに対して行う探索方法です。
二分探索(アルゴリズムC 第2巻 p.8)
真ん中のデータが見つけたいデータかどうか調べます。
見つけたいデータが真ん中のデータより小さければ左側に対して、
大きければ右側に対して、同じことを繰り返します。
内挿探索(アルゴリズムC 第2巻 p.12)
二分探索は真ん中を調べていましたが、内挿探索では
の場所を調べます。これは二分探索とは違い、
データの数値から見つけたいデータがどのあたりにあるか推測しています
(二分探索は数値は見ない)。
この例ではどちらの探索も二回で見つけていますが、データが大きくなった場合は 圧倒的に内挿探索の方が回数が少なく済みます。
二分探索、内挿探索を用いてデータを探索するプログラムを作成しなさい。 プログラムは以下の条件を満たすこと。(ex10-2-skel.c)
実行例: % ./a.out data: 1 4 6 9 10 13 19 23 25 30 Input key for binary search: 9 found. Input key for interpolation search: 9 found. % ./a.out data: 1 4 6 9 10 13 19 23 25 30 Input key for binary search: 8 not found. Input key for interpolation search: 8 not found.
データは、例えば次のように、配列を宣言するときに初期化しても良いです。 ただし、これらの探索方法はデータがソートされていることが前提なので、 ソートされた状態で初期化するようにしてください。
int a[N]={ 1, 4, 6, 9, 10, 13, 19, 23, 25, 30 };
内挿探索関数は、二分探索関数の x=(l+r)/2;
の部分を
x=l+(v-a[l])*(r-l)/(a[r]-a[l]);
に変更すればできます
(アルゴリズムC 第2巻 p.12)
。
二分探索、内挿探索において、探索終了までの 比較回数を数え、表示するプログラムを作成しなさい。(ex10-3-skel.c) プログラムは以下の条件を満たすこと。
また、問題2の内挿探索関数では、データによっては無限ループ (または segmentation fault になる)場合があるので、これも直しなさい
実行例: % ./a.out data: 9 10 16 20 20 25 31 40 41 47 50 60 63 65 67 67 73 77 78 83 84 84 86 87 91 92 99 Input key for binary search: 99 found. Number of Comparison: 10 Input key for interpolation search: 99 found. Number of Comparison: 2
問題2の内挿探索関数は、
分母( a[r]-a[l]
)が 0 になる場合や、
分子(v-a[l]
)が負になる場合がまったく考慮されていません。
こうならないように改良してください。