プログラミングの問題で、二分探索をあまり理解していないのですが、どなたか教えて頂けないでしょうか?
よろしくお願いします。
Q1. 二分探索を行なっていて、配列のhead番目以上tail番目以下に探している数があることがわかっているとする。 head番目とtail番目の真ん中(i番目)が探している数より大きかった時、 探している数が存在する範囲として、最も適切なものを選びなさい。
1. head〜i-1
2. head〜i
3. i〜tail
4. i+1〜tail
Q2. 二分探索を行なっている時、求める値の存在する範囲が、配列のhead番目以上、tail番目以下の 範囲であるとする。headとtailの間隔を狭める様に、この2つの値を変えていくわけだが、 headとtailがどの様な関係になった時に、この配列に求める値が存在しないと言うことができるか? 最も適切なものを選びなさい。
1. head < tail
2. head == tail
3. head >= tail
4. head > tail
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
トランプを用意して手作業でやってみると分かりやすいと思います。
準備として1つのスート分を1~Kの順に並べます。
1.トランプの束を半分取る。
2.とった時に残った時のカードの数字が目的の数字より小さい場合は、残ったカードの束を3で使う。数字より小さい大きい場合は、手に取ったカードの束を3で使う。目的のカードが出たら終了。
3.目的の数字が出るまで1~2を繰り返す。
例えば目的のカードを8とした場合…
1-1回目.13枚の半分(切り捨て)の6枚を取る。
2-1回目.7が出たので残ったカードを使う。
1-2回目.残った7枚の半分の3枚を取る。
2-2回目.10が出たので手に取ったカードを使う。
1-3回目.手に取った3枚の半分1枚を取る。
2-3回目.目的のカード(8)が出たので終了。
という動きになります。
こうやって目的のカードを探した時に、カードが最初の並びで何番目だったかを返却しているのが二分探索です。
上の例では連続したカードですが、「カードが最初の並びで何番目だったかを返却する」事でデータが歯抜けの状態でも問題なくなります。
例えば、「1,3,4,6,11」の様な数字列でも見つけ出すことができます。
アルゴリズムは図や文章で開設される事が多いですが、そのまま理解する事はそれほど簡単ではありません。
自分でやってみると「こんな事が起こっているのか」と視覚的に分かるので是非手作業でやってみる事をお勧めします。
No.1
- 回答日時:
配列にセットされている値はheadからtailに向かってだんだん大きくなるように並んでいますか?
それともその逆ですか?
問題文をそういったことを考慮しながらよく読んで、二分検索法で求める値を探していく際の様を頭の中に浮かべながら考えるとよいです。
で、プログラム言語で考えない方がよいです。あくまで日常使っている言語と数が並んだ図で考えましょう。あとはチャート図ですか。
以下参考に。
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86 …
ちなみにGoogleなどで「二分検索」とか「バイナリーサーチ」といったキーワードで検索すると様々な解説ページがヒットするかと思います。
そういう物の中からご自身にあった(=分かりやすいと思える)ものを選ばれるとよいです。
参考まで。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 英語 魚の胴体 7 2022/12/24 19:07
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- 英語 “I don’t give a rat’s tail ” 2 2023/06/30 10:00
- マンガ・コミック マガジンで連載されていたFAIRY TAILは大ヒット作品ですか? 1 2022/06/24 12:10
- JavaScript html5に変えるとスライドショーが消えてしまった。 3 2022/03/26 19:53
- JavaScript switch文のswitch(n)の部分を複数の値にするか、if文に変えてほしいです。 1 2022/07/27 17:18
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- JavaScript javascriptのちょっとした動作不良(原因は突き止めたのですが) 1 2023/06/15 19:58
- JavaScript javascript作成してます。ラジオボタンで判定するコードを書いてます。 1 2023/07/18 11:03
- マンガ・コミック マガジンで連載されていたFAIRY TAILは知名度はどれぐらいですか? 1 2022/06/24 12:13
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
配列数式の解除
-
ListViewで、非表示列って作れ...
-
特定のセル範囲で4文字以上入力...
-
2つ以上の変数を比較して最大数...
-
VB6 配列を初期化したい
-
VBA 1次元配列を2次元に追加する
-
配列で飛び飛びの値を指定して...
-
VBA 1つの列を3つ以上の条件で...
-
Excel VBA配列をFunctionに渡す
-
配列変数の添字が範囲外ですと...
-
VBA Match関数の限界
-
OutlookVBAでサブフォルダ一括作成
-
Excel-VBAの配列「Public Const...
-
シェルスクリプト中で、ヒアド...
-
【VBA】配列とWorksheetFunctio...
-
for each の現在の配列ポインタ...
-
えfor文とか使っちゃう時点で時...
-
verilogで配列の任意の8bitを取...
-
コントロール配列のループ
-
2次元動的配列の第一引数のみを...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
配列数式の解除
-
2つ以上の変数を比較して最大数...
-
VBA 1次元配列を2次元に追加する
-
特定のセル範囲で4文字以上入力...
-
for each の現在の配列ポインタ...
-
VBのFunctionで、配列を引数...
-
subの配列引数をoptionalで使う...
-
VB6 配列を初期化したい
-
ListViewで、非表示列って作れ...
-
配列変数の添字が範囲外ですと...
-
Excel-VBAの配列「Public Const...
-
2次元動的配列の第一引数のみを...
-
VBAで近似曲線の係数取得
-
VLOOKUP関数で、一番下...
-
配列に同じ値を入れる方法
-
エクセルで最小値から0を除く方法
-
linest関数に配列を渡す
-
配列を任意の数値で埋める方法
-
Dim は何の略ですか?
-
配列内の内容を全て表示する方法
おすすめ情報