001 - プログラミング入門：二分探索

時間制限 2 秒 / メモリ制限 256 MB / 得点 100 / x 6 /

TLE
2sec
MLE
256MB
得点
100

この問題は、ソースコードを公開に設定しているので、
暇な人は初めてこの問題に取り組む人の為に
分かりやすいソースコードを提出してくださると助かります。

二分探索

ある条件を満たす最小の数等を求めるときに使いますが、
汎用性が高く、覚えて損無し覚えず損ばかりの考え方です。

たとえば、左から順番に小さい順に並べられたデータがN個あるとします。
この中から T以下の値の個数を求めるアルゴリズムを考えます。
単純にデータの i番目の値がTより小さいかを判断し、
Tより大きくなったらその時の i-1 を出力すれば正しい結果が求められます。
この考え方を 線形探索 と呼びます。たぶん。

しかし、この解法を用いると、最大N回の判断が必要になってしまいます。
更に、この処理をM回行うとすると、最大 M*N回判断が必要になることが分かります。

ここで注目するべきなのは、
a番目の値がTより大きかった場合、
数は小さい順に並んでいるため、
(a < i) である i番目の値は全てTより大きいのが分かる
という点です。
当然その逆も然り、
a番目の値がTより小さかった場合、
数は小さい順に並んでいるため、
(i < a) である i番目の値は全てTより小さいのが分かる
といえます。

このことを利用すると、最大の判断回数を大きく減らすことが出来ます。
最初に1 ~ N番地の真ん中の番地(N/2番地)の値を見て、
大きかったら1 ~ N/2の真ん中の番地の値を見る、
小さかったらN/2 ~ Nの真ん中の番地の値を見る、
を繰り返していくことによって、
探索の対象となる範囲を半分ずつに削ることができます。
このような考え方を、二分探索と呼びます。

具体的な疑似ソースを以下に示します。

探索の対象となる範囲の左端の番地を始まりの番地に、右端の番地を終わりの番地に設定。
while( 左端の番地 < 右端の番地 ){
　　調べる番地 = (左端の番地 + 右端の番地)/2 ;
　　if( 調べた番地の値がＴより大きい ){
　　　　右端の番地 = 調べた番地 - 1 ;
　　}
　　else {
　　　　左端の番地 = 調べた番地 + 1 ;
　　}
}

当然ですが、上記のソースは今回の問題に対しての例であり、
問題によっては上記のソースに対して臨機応変に処理を書き換える必要があります。
ソースで覚えるのではなく、ソースがどんな動作を行っているのかを理解してください。
分からないことが有れば各々の先輩に聞いてください。
それでは、以下の問題を解いてみましょう。

問題

N個の整数データと、M個の命令が与えられます。
データは与えられる順に、1,2,3, ... ,N 個目と表します。
データは小さい順にソートされています。
命令は以下のようになっています。

T

この命令では、Tが入力されるので、
与えられたデータの中に、T以下の値がいくつあるかを出力してください。
詳しくは、入出力例を参考にしてください。

制約

  • 1 ≦ N ≦ 1,000,000
  • 1 ≦ M ≦ 100,000
  • 0 ≦ Datai , T ≦ 1,000,000,000
  • Datai ≦ Datai+1

部分点

配点の20%分は N,M ≦ 1000 を満たします。
これは、線形探索でTLEにならない範囲です。

入出力形式

入力形式

N
Data1 Data2 ... DataN
M
T1
T2
..
..
..
TM

出力形式

命令毎に、T以下の値の数を出力し改行してください。

入出力例

入力例

5
10 20 30 40 50
3
20
35
8

出力例

2
3
0

一つめの命令では、20 が与えられます。
20 以下の値は 10 , 20 なので 2 を出力します。
二つめの命令では、35 が与えられます。
35 以下の値は 10 , 20 , 30 なので 3 を出力します。
三つめの命令では、8 が与えられます。
8 以下の値は一つもないので 0 を出力します。