【２分探索】
　　　整列されたデータを探索キーとの比較によって、可能性のある領域を半分ずつに狭めていく探索法。
　　　効率のよい探索ができる。
　　　配列中のデータが昇順、又は降順に並んでいることが前提となる。
　　　最大探索回数（比較回数）の求め方を覚えること。

　　　データがｎ個ある場合には、２を底とする対数を使って
　　　　　　ｌｏｇ２（ｎ）
　　　と表される（端数は切り上げ）。

　　　（ただし、２，４，８，１６，３２など２のｎ乗にあたる数値の場合には
　　　ｌｏｇ２（ｎ）＋１となることに注意）。

　　　データ数が　２〜　３（２の１乗以上２乗未満）：最大探索回数は２回
　　　データ数が　４〜　７（２の２乗以上３乗未満）：最大探索回数は３回
　　　データ数が　８〜１５（２の３乗以上４乗未満）：最大探索回数は４回
　　　データ数が１６〜３１（２の４乗以上５乗未満）：最大探索回数は５回
　　　　：　　　　　　　　：　　　　　　　　　：
　　　　：　　　　　　　　：　　　　　　　　　：
　　　以下、これの繰り返し。

　　　例）
　　　　１０個のデータあり、次のように昇順で格納されている時
　　　　　「６」のデータを探索する。
　　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　　│　１│　２│　３│　４│　５│　６│　７│　８│　９│１０│
　　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　　　まず全体の真ん中である５番目の要素をチェックする。
　　　　　　　　　　　　　　　　　チェック
　　　　　　　　　　　　　　　　　　↓
　　　　┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
　　　　│　１│　２│　３│　４│　５│　６│　７│　８│　９│１０│
　　　　└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
　　　　次に、検索のキーである「６」とチェック対象の「５」を比較すると
　　　　　　　５＜６　より
　　　　該当するデータは「５」より右にあることになる。
　　　　　　　　　　　　　┌──┬──┬──┬──┬──┐
　　　　　　　　　　　　　│　６│　７│　８│　９│１０│
　　　　　　　　　　　　　└──┴──┴──┴──┴──┘
　　　　６より右側の５つのデータのうち、真ん中の３番目の要素をチェックする。
　　
　　　　　　　　　　　　　　　　　　　　チェック
　　　　　　　　　　　　　　　　　　　　　↓　　　　　　　　　　　　
　　　　　　　　　　　　　┌──┬──┬──┬──┬──┐
　　　　　　　　　　　　　│　６│　７│　８│　９│１０│
　　　　　　　　　　　　　└──┴──┴──┴──┴──┘
　　　　次に、検索のキーである「６」とチェック対象の「８」を比較すると
　　　　　　　６＜８　より
　　　　該当するデータは「８」より左にあることになる。
　　　　　　　　　　　　　　　　┌──┬──┐
　　　　　　　　　　　　　　　　│　６│　７│
　　　　　　　　　　　　　　　　└──┴──┘
　　　　２度目のチェックで残った８より左側の２つのデータのうち、１番目の
　　　　要素をチェックする。
　　　　　　　　　　　　　　　　　チェック
　　　　　　　　　　　　　　　　　　↓
　　　　　　　　　　　　　　　　┌──┬──┐
　　　　　　　　　　　　　　　　│　６│　７│
　　　　　　　　　　　　　　　　└──┴──┘
　　　　検索のキーである「６」とチェック対象の「６」を比較すると
　　　　　　　６＝６　となり探索完了となる。


　　　ポイント）
　　　　２分探索に関しては、最大探索回数がポイントになる。

　　　例）
　　　　２，０００個の相異なる要素が，キーの昇順に整列された表がある。
　　　　外部から入力したキーによってこの表を２分探索して、該当するキーの
　　　　要素を取り出す。このときのキーの比較回数は最大何回になるか。
　　　　ただし、該当するキーは必ず表中にあるものとする。

　　　　　公式通り　ｌｏｇ２（２０００）　を求める。
　　　　　２＾１０＝２の１０乗＝１０２４
　　　　　２＾１１＝２の１１乗＝２０４８
　　　　　　　　であるから、
　　　　　１０＜ｌｏｇ２（２０００）＜１１
　　　　　となり、端数は切り上げになるので１１回となる。


　　　参考）
　　　　対数（ｌｏｇ）
　　　　　べき乗を＾、Ｎを底とする対数をｌｏｇＮ（ｘｘ）と表す。
　　　　　２＾５＝２×２×２×２×２＝３２
　　　　　であるから、対数で表すと
　　　　　　　　　　ｌｏｇ２（３２）＝５
　　　　　ということになる。このとき２を底（てい）と呼ぶ。
　　　　　つまりこの関数は、３２は２の何乗になっているかを求めている。
　　　　　この式を覚えておくだけでもずっと違ってくるので、覚えておいた方が
　　　　　良い。底としてよく使われるのは、試験では２である。


【線形探索法】
　　　表の先頭の要素から順番に調べていく探索アルゴリズム。
　　　データが整列されている必要はない。
　　　データがｎ個ある場合の最大探索回数はｎ。
　　　平均探索回数はｎ／２回になる。


【番兵法】
　　　線形探索法で探索効率を上げるための手法として「番兵法」というものがある。

　　　通常の線形探索だと、１つのデータに対して２回のチェックが必要となる。
　　　　　・そのデータが探索対象であるかどうかの比較
　　　　　・そのデータが探索範囲の最終データであるかどうかの比較
　　　これに対して番兵法では番兵と呼ばれる探索の対象となっているデータを
　　　探索対象の最後に付け加える。これにより、
　　　　・そのデータが探索範囲の最終データであるかどうかの比較をする必要が
　　　　　なくなる。
　　　番兵法では、
　　　　　・そのデータが探索対象であるかどうかの比較だけを行う。
　　　必ず探索対象のデータが存在しているからである。さらに、探索結果として
　　　得られたデータの格納位置をチェックして、それが番兵であったら
　　　探索対象がなかったと判断する。
　　　比較の回数をほぼ半減することで、データが大量のときには、探索速度が
　　　結構速くなる。

　　　番兵→検索の際にダミー・データを使用することで、
　　　処理を簡潔化するための手法である。配列のうちの
　　　データを格納している要素の直後（Ａ[ｎ＋１］）に
　　　番兵をおくことで、繰り返し条件の判定が不要となる。
　　　Ａ［ｉ］とＸが等しくなったときのｉがｎより大きい（ｎ＋１）の
　　　場合は、番兵との比較まで繰り返したことになるので、
　　　求めるデータはなかった。
　　　　　　　　＿＿＿＿＿
　　　　　　　（　開　始　）
　　　　　　　　￣￣│￣￣
　　　　　　　┌──┴──┐
　　　　　　　│x→ A[n+1]│
　　　　　　　└──┬──┘
　　　　　　　┌──┴──┐
　　　　　　　│　1 → i　│
　　　　　　　└──┬──┘
　　　　　┌───→│
　　　　　│　　　／　＼
　　　　　│　　／A[i]:x＼　＝
　　　　　│　　＼　　　／―――――┐
　　　　　│　　　＼　／　　　　　　│
　　　　　│　　　　│≠　　　　　／　＼
　　　　　│　┌──┴──┐　　／ i : n＼　＞
　　　　　│　│ i+1 → i │　　＼　　　／―――――┐
　　　　　│　└──┬──┘　　　＼　／　　　　　　│
　　　　　└――――┘　　　　　　　│≦　　　　　　│
　　　　　　　　　　　　　　　　──┴──　　　──┴──
　　　　　　　　　　　　　　　（　成　功　）　（　失　敗　）
　　　　　　　　　　　　　　　　￣￣￣￣￣　　　￣￣￣￣￣