うごく基本情報

平成24年度 秋期 問6

アルゴリズムとプログラミング › 探索アルゴリズム △ ときどき出る

出典:平成24年度 秋期 基本情報技術者試験 午前 問6 の問題

出典:平成24年度 秋期 基本情報技術者試験 午前 問6

正解と解説を見る

正解:イ

覚えること:2分探索の中央 =(下端 + 上端)÷ 2(切捨て)。見つからなければ範囲を半分に狭める。

探索範囲は x から y までなので、中央の添字は (x + y) / 2 です(イ)。k が A(m) より小さければ上端を m − 1 に、大きければ下端を m + 1 にして範囲を半分に絞ります。アの (x + y) は 2 で割っていないので、範囲の外の添字になります。ウの (x − y) / 2 は負の数になります。エの (y − x) / 2 は範囲の幅の半分で、下端の x を足していないので、範囲の真ん中になりません。

解説はこのサイトが作成したものです。