真ん中のデータが見つけたいデータかどうか調べます。 見つけたいデータが真ん中のデータより小さければ左側に対して、 大きければ右側に対して、同じことを繰り返します。
データの中から、あるデータを探すことを探索といいます。 ここでは二分探索 （アルゴリズムＣ 第２巻 p.8） を用いて探索を行います。
次のようなソートされたデータがある。
1 4 6 9 10 13 19 23 25 30
(1) このデータから二分探索を用いて 9
を探索する過程を書きなさい。
(2) このデータから内挿探索を用いて 9
を探索する過程を書きなさい。
二分探索、内挿探索はソートされているデータに対して行う探索方法です。
二分探索（アルゴリズムＣ 第２巻 p.8）
真ん中のデータが見つけたいデータかどうか調べます。
見つけたいデータが真ん中のデータより小さければ左側に対して、
大きければ右側に対して、同じことを繰り返します。
内挿探索（アルゴリズムＣ 第２巻 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]); に変更すればできます
（アルゴリズムＣ 第２巻 p.12）
。
二分探索、内挿探索において、探索終了までの 比較回数を数え、表示するプログラムを作成しなさい。（ex10-3-skel.c） プログラムは以下の条件を満たすこと。
また、問題２の内挿探索関数では、データによっては無限ループ （または 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
問題２の内挿探索関数は、
分母（ a[r]-a[l]）が 0 になる場合や、
分子（v-a[l]）が負になる場合がまったく考慮されていません。
こうならないように改良してください。