アルゴリズムトップ
0. はじめに
1. アルゴリズム
1. アルゴリズムとは
2. 当ページの範囲
3. 良いアルゴリズム
4. フローチャートの書き方(記号)
5. フローチャートの書き方(構造)
6. 順次構造
7. 分岐構造
8. 反復構造
2. 順次構造
1. 代入
2. 計算
3. 入力
4. 出力
5. 練習問題1
6. 練習問題2
3. 分岐構造
1. 条件分岐
2. 単一分岐
3. 練習問題1
4. 多重分岐
5. 複合条件
6. ケース(多方向分岐)
7. 練習問題2
8. 練習問題3
4. 反復構造
1. 反復構造の種類
2. 前判定型
3. 後判定型
4. 練習問題1
5. 練習問題2
6. 練習問題3
7. 多重反復処理(ネスト)
8. 練習問題4
9. 練習問題5
5. 配列
1. 配列とは
2. 練習問題
3. 2次配列
4. 練習問題
5. 素数を求める,その1
6. 素数を求める,その2
6. 検索・ソート
1. サブルーチン
2. シーケンシャルサーチ
3. バイナリサーチ
4. 練習問題
5. ルックアップテーブル
6. ソートとは
7. 選択法
8. 交換法
9. バブルソート
10. 挿入法
11. クイックソート
12. 処理速度の比較
7. 文字列
1. 文字と文字列
2. 文字列処理
3. 文字列のコピー
4. 練習問題
5. 文字列の比較
6. 文字列の連結
7. 文字列の検索
| |
前ページへ : トップへ : 練習問題へ
- 6-3.バイナリーサーチ
-
「数当てゲームです。1から20までのある数字があります。これを当ててください。ただし、
答えた数よりも大きいか、小さいかは教えてあげます。」と言われた場合、どうすれば
答える回数が少なくてすむでしょうか?
例) 答えが7の場合
- 10? ・・・ 小さい
- 5? ・・・ 大きい
- 7? ・・・ 正解
|
と答えるのがベストです。どういう根拠でしょう?
・まずはじめは、1〜20の範囲がありますので、その中間の10を言ってみます
・10よりも小さいので1〜9の範囲に縮まりました
・そこで1〜9の中間の5を言ってみます
・5よりも大きいので6〜9の範囲になりました
・その中間の7にしたところ、正解でした
この方法は、上限、下限の範囲を狭めていく方法で、1回の質問(照合)で
範囲が半分になる。したがって要素数が1000の場合、その平均照合回数は
log21000≒10回と、先に述べた、シーケンシャルサーチの
1000÷2≒500回と比べてかなり効率がよいことがわかる。
ただし、データが昇順に並んでいないと検索できないという欠点がある。
前ページへ : トップへ : 練習問題へ
|