基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
同じ値の出現数を二つの境界で求める
条件を整理し、答えを選んでから解き方を確認しましょう。
昇順A=[1,2,2,2,5,7]、添字0〜5。境界関数B(t)はt以上が初めて現れる位置（なければ6）を返す。整数値2の個数を求める。 B(t): lo ← 0 hi ← 6 while lo < hi m ← floor((lo+hi)/2) if A[m] < t lo ← m + 1 else hi ← m endif endwhile return lo 件数を求める式と値はどれか。
答え・解き方を読む
B(3)−B(2)=3
図で見る
2以上と3以上の最初の位置
図を拡大して見る ↗2以上が最初に現れる添字は1、3以上は添字4の値5。半開区間[1,4)に値2が3個あるのでB(3)−B(2)=3。
添字は0始まりです。B(3)は値3の位置を探すのではなく、3以上が初めて現れる位置を返します。
考える順序
- 1B(2)=1で2の区間が始まる
- 2整数なのでB(3)=4が2の区間の直後
- 3半開区間[1,4)の長さは4−1=3
選択肢ごとの理由
- 比較 · B(3)−B(2)+1=4
終端は区間に含まれないため1を加えません。
- 比較 · B(2)+B(3)=5
位置の合計では区間長を得られません。
- 正解 · B(3)−B(2)=3
B(2)=1で2の区間が始まる。整数なのでB(3)=4が2の区間の直後。半開区間[1,4)の長さは4−1=3。
- 比較 · B(2)−B(1)=1
それは1の区間の長さを求めています。