問題

長さ n の単調非減少な数列 a0,…,an–1 と、数 k が与えられます。

ai ≧ k となるような最小の i を求めなさい。

存在しない場合は n を出力しなさい。

方針

二分探索でとく。基本的な二分探索の問題.

解答

gn = 5
a = [2, 3, 3, 5, 6]
k = 3


lb = -1
ub = n

while ub - lb > 1:
    mid = (lb + ub) / 2

    if a[mid] >= k:
        ub = mid
    else:
        lb = mid

print ub