FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：昇順配列 a={1,2,2,2,4,5,5} に対して、次の…
問題
昇順配列 a={1,2,2,2,4,5,5} に対して、次の手続 countKey(a,2) を実行したときの戻り値はどれか。
○整数型: countKey(整数型の配列: a, 整数型: key) 整数型: lb ← key以上となる最初の添字 整数型: ub ← keyより大きくなる最初の添字 lbとubはいずれも二分探索で求める return ub － lb
- ア 2
- イ 3（正解）
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
2以上となる最初の位置 lb は2です。2より大きくなる最初の位置 ub は5です。したがって、値2がある範囲は添字2,3,4で、個数は ub-lb=5-2=3 です。
2は最初と最後の添字差をそのまま数えた場合に出やすいです。4はubの位置も2の個数に含めてしまった誤りです。5はubそのものを答えた途中値です。
重複数を二分探索で求めるときは、lowerBoundとupperBoundの差を使います。upperBoundは最後の要素位置ではなく、範囲の右端の次の位置です。
このアルゴリズムの正体：これは整列済み配列で特定の値の個数を数える定番手法で、lowerBound（key以上の最初の位置）とupperBound（keyより大きい最初の位置）の差をとります。要素を一つずつ走査すると要素数に比例しますが、二分探索を2回行うこの方法なら配列が大きくても各探索が対数オーダーで済み、重複が多い値でも高速に件数を求められます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。